列印給定二進位制矩陣中的唯一行

---

在計算機科學中，二進位制矩陣佔據著非常重要的地位，包含大量資訊，因為資料是使用 0 和 1 來表示的，這是計算機的語言。在二進位制矩陣中，唯一行指的是與矩陣中任何其他行都不相同的行。每行唯一行包含唯一的資訊，這些資訊在矩陣中的其他任何地方都不存在，除了該行本身。發現這些唯一行可以提供有關行之間關係、矩陣中的模式以及關鍵元素識別方面的資訊。

問題陳述

給定一個包含 0 和 1 的二進位制矩陣 mat[]。任務是列印矩陣的所有唯一行。

示例 1

輸入

mat[][] = 
{{1, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1}}

輸出

1 0 1 1 0
0 1 0 0 0
0 1 0 0 1

解釋

In the given matrix, row1 = 1 0 1 1 0
row2 = 0 1 0 0 0
row3 = 1 0 1 1 0
row4 = 0 1 0 0 1
Since, row1 = row3 so unique rows are row1, row2 and row4.

示例 2

輸入

mat[][] = 
{{1, 0, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 0, 1, 1, 0}}

輸出

1 0 1 1 0

解釋

In the given matrix, row1 = 1 0 1 1 0
row2 = 1 0 1 1 0
row3 = 1 0 1 1 0
row4 = 1 0 1 1 01

由於所有行都相等，因此唯一行是第 1 行。

方法 1：蠻力方法

該問題的蠻力解決方案是首先列印矩陣的第一行，然後對於每一行，檢查前面的行以檢查是否存在重複。

虛擬碼

function uniqueRows(mat: boolean[row][col], i: integer) -> boolean
   flag <- false    
   for j from 0 to i - 1
      flag <- true        
      for k from 0 to col
         if mat[i][k] ≠ mat[j][k]
            flag <- false
            exit loop            
      if flag = true
         break loop    
   return flag

示例：C++ 實現

以下程式碼列印二進位制矩陣中的唯一行。

#include <bits/stdc++.h>
using namespace std;
#define row 4
#define col 5

// Function used to determine if a row is unique or not
bool uniqueRows(bool mat[row][col], int i){
   bool flag = 0;
   for (int j = 0; j < i; j++){
      flag = 1;
      for (int k = 0; k <= col; k++)
         if (mat[i][k] != mat[j][k])
            flag = 0;
      if (flag == 1)
         break;
   }
   return flag;
}
int main(){
   bool mat[row][col] = {{1, 0, 1, 1, 0},
      {0, 1, 0, 0, 0},
      {1, 0, 1, 1, 0},
      {0, 1, 0, 0, 1}};
   for (int i = 0; i < row; i++) {
      if (!uniqueRows(mat, i)) {
         for (int j = 0; j < col; j++) {
            cout << mat[i][j] << " ";
         }
         cout << endl;
      }
   }
   return 0;
}

輸出

1 0 1 1 0 
0 1 0 0 0 
0 1 0 0 1

時間複雜度 - O(col * row^2)

空間複雜度 - O(1)

方法 2：使用 Trie

使用 Trie 資料結構的方法是將每一行插入到具有 2 個字母大小的 Trie 中。如果之前見過該行，則不列印它，否則列印新唯一行。

虛擬碼

struct Trie
   leaf: boolean
   c: array of Trie pointers

function newNode() -> Trie pointer
   node <- new Trie
   node.c <- array of Trie pointers with size 2
   node.c[0] <- null
   node.c[1] <- null
   node.leaf <- false
   return node

function insert(head: reference to Trie pointer, arr: array of booleans) -> boolean
   ptr <- head
   for i from 0 to col - 1
      if ptr.c[arr[i]] = null
         ptr.c[arr[i]] <- newNode()
      ptr <- ptr.c[arr[i]]
   if ptr.leaf = true
      return false
   ptr.leaf <- true
   return true

示例：C++ 實現

以下程式碼列印二進位制矩陣中的唯一行。

#include <iostream>
using namespace std;
#define row 4
#define col 5
// Structure of trie
struct Trie {
   bool leaf;
   Trie *c[2];
};
// function to create new trie node
Trie *newNode(){
   Trie *node = new Trie;
   node->c[0] = node->c[1] = nullptr;
   node->leaf = false;
   return node;
}
// Function to insert elements of matrix to trie
bool insert(Trie *&head, bool *arr){
   Trie *ptr = head;
   for (int i = 0; i < col; i++) {
      if (ptr->c[arr[i]] == nullptr) {
         ptr->c[arr[i]] = newNode();
      }
      ptr = ptr->c[arr[i]];
   }
   // row inserted before
   if (ptr->leaf) {
      return false;
   }
   // new unique row; mark leaf node
   return ptr->leaf = true;
}
int main(){
   bool mat[row][col] = {{1, 0, 1, 1, 0},
      {0, 1, 0, 0, 0},
      {1, 0, 1, 1, 0},
      {0, 1, 0, 0, 1}};
   Trie *head = newNode();
   for (int i = 0; i < row; i++) {
      if (insert(head, mat[i])) {
         for (int j = 0; j < col; j++) {
            cout << mat[i][j] << " ";
         }
         cout << endl;
      }
   }
   return 0;
}

輸出

1 0 1 1 0 
0 1 0 0 0 
0 1 0 0 1

時間複雜度 - O(col * row)

空間複雜度 - O(col * row)

方法 3：十進位制

該方法是將輸入矩陣中的每一行轉換為十進位制數。我們手頭剩下的任務將是比較所有十進位制數並刪除所有重複項並列印唯一對。

虛擬碼

function uniqueRow(mat: boolean[row][col], i: integer, set: unordered_set of integers) -> boolean
   decimal <- 0
   flag <- false    
   for j from 0 to col - 1
      decimal <- decimal + mat[i][j] * 2^j    
   if decimal is in set
      flag <- false
   else
      flag <- true
      insert decimal into set    
   return flag

示例：C++ 實現

以下程式碼列印二進位制矩陣中的唯一行。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;
#define row 4
#define col 5

// Function to find the unique row in the matrix
bool uniqueRow(bool mat[row][col], int i, unordered_set<unsigned> &set){
   unsigned decimal = 0;
   bool flag;
   for (int j = 0; j < col; j++){
      // Decimal equivalent
      decimal += mat[i][j] * pow(2, j);
   }
   // Duplicate row
   if (set.find(decimal) != set.end()){
      flag = 0;
   }
   // Unique row
   else {
      flag = 1;
      set.insert(decimal);
   }
   return flag;
}
int main() {
   bool mat[row][col] = {{1, 0, 1, 1, 0},
      {0, 1, 0, 0, 0},
      {1, 0, 1, 1, 0},
      {0, 1, 0, 0, 1}};
   unordered_set<unsigned> set;
   for (int i = 0; i < row; i++) {
      if (uniqueRow(mat, i, set)) {
         for (int j = 0; j < col; j++) {
            cout << mat[i][j] << " ";
         }
         cout << endl;
      }
   }
   return 0;
}

輸出

1 0 1 1 0 
0 1 0 0 0 
0 1 0 0 1

時間複雜度 - O(col * row)

空間複雜度 - O(col)

結論

總之，給定的解決方案和程式碼提供了有效的解決方案來識別和列印二進位制矩陣中的唯一行。此問題在資料分析和模式識別等領域具有實際應用。