打印给定二进制矩阵中的唯一行

---

在计算机科学中，二进制矩阵占据着非常重要的地位，包含大量信息，因为数据是使用 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)

结论

总之，给定的解决方案和代码提供了有效的解决方案来识别和打印二进制矩阵中的唯一行。此问题在数据分析和模式识别等领域具有实际应用。