原文：
给定一个二进制矩阵，打印给定矩阵的所有唯一行。
示例：
input:
{0, 1, 0, 0, 1}
{1, 0, 1, 1, 0}
{0, 1, 0, 0, 1}
{1, 1, 1, 0, 0}
output:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0
explanation:
the rows are r1={0, 1, 0, 0, 1},
r2={1, 0, 1, 1, 0}, r3={0, 1, 0, 0, 1},
r4={1, 1, 1, 0, 0}, as r1 = r3, remove r3
and print the other rows.
input:
{0, 1, 0}
{1, 0, 1}
{0, 1, 0}
output:
0 1 0
1 0 1
explanation:
the rows are r1={0, 1, 0},
r2={1, 0, 1}, r3={0, 1, 0} as r1 = r3,
remove r3 and print the other rows.
方法 1：此方法说明解决上述问题的简单方法。
-
方法：一种简单的方法是使用所有已处理的行检查每一行。 打印第一行。 现在，从第二行开始，针对每一行，将该行与已处理的行进行比较。 如果该行与任何已处理的行匹配，请跳过该行，否则将其打印出来。
-
算法：
-
遍历矩阵的行。
-
对于每一行，检查是否有比当前索引少的相似行。
-
如果任何两行相似，则不要打印该行。
-
否则打印该行。
-
-
实现：
```
// given a binary matrix of m x n of integers, // you need to return only unique rows of binary array
using namespace std;
// the main function that prints // all unique rows in a given matrix. void finduniquerows(int m[row][col]) { //traverse through the matrix for(int i=0; i
//check if there is similar column //is already printed, i.e if i and //jth column match. for(int j=0; j
for(int k=0; k<=col; k ) if(m[i][k]!=m[j][k]) flag=0;
if(flag==1) break; }
//if no row is similar if(flag==0) { //print the row for(int j=0; j
// driver code int main() { int m[row][col] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {1, 0, 1, 0, 0}};
finduniquerows(m);
return 0; }
```
输出：
``` 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0
```
-
复杂度分析：
-
时间复杂度：
o(row ^ 2 x col)。因此，对于每一行，请检查是否还有其他类似的行。 因此，时间复杂度为
o(row ^ 2 x col)。 -
辅助空间：
o(1)。由于不需要额外的空间。
-
方法 2：此方法使用解决上述操作。 二分搜索树是基于节点的二进制树数据结构，具有以下属性：
-
节点的左子树仅包含键号小于节点键号的节点。
-
节点的右子树仅包含键大于该节点的键的节点。
-
左和右子树也都必须是二叉搜索树。
-
不得有重复的节点。
二分搜索树的上述属性提供了键之间的顺序，因此可以快速完成搜索，最小和最大等操作。 如果没有顺序，那么我们可能必须比较每个键以搜索给定的键。
-
方法：该过程必须从找到每行的十进制等效项并将它们插入 bst 开始。 众所周知，bst 的每个节点将包含两个字段，一个字段用于十进制值，另一字段用于行号。 如果节点重复，则不得插入该节点。 最后，遍历 bst 并打印相应的行。
-
算法：
-
创建一个 bst，在其中不能存储任何重复的元素。 创建一个函数以将行转换为十进制，并将十进制值转换为二进制数组。
-
遍历矩阵并将该行插入 bst。
-
遍历 bst（有序遍历）并将十进制转换为二进制数组并打印。
-
-
实现：
```
// given a binary matrix of m x n of integers, // you need to return only unique rows of binary array
using namespace std;
class bst { int data; bst left, right;
public:
// default constructor. bst();
// parameterized constructor. bst(int);
// insert function. bst insert(bst , int);
// inorder traversal. void inorder(bst *); };
//convert array to decimal int convert(int arr[]) { int sum=0;
for(int i=0; i
//print the column represented as integers void print(int p) { for(int i=0; i
// default constructor definition. bst :: bst() : data(0), left(null), right(null){}
// parameterized constructor definition. bst :: bst(int value) { data = value; left = right = null; }
// insert function definition. bst bst :: insert(bst root, int value) { if(!root) { // insert the first node, if root is null. return new bst(value); }
//if the value is present if(value == root->data) return root;
// insert data. if(value > root->data) { // insert right node data, if the 'value' // to be inserted is greater than 'root' node data.
// process right nodes. root->right = insert(root->right, value); } else { // insert left node data, if the 'value' // to be inserted is greater than 'root' node data.
// process left nodes. root->left = insert(root->left, value); }
// return 'root' node, after insertion. return root; }
// inorder traversal function. // this gives data in sorted order. void bst :: inorder(bst *root) { if(!root) { return; } inorder(root->left); print( root->data ); inorder(root->right); }
// the main function that prints // all unique rows in a given matrix. void finduniquerows(int m[row][col]) {
bst b, *root = null;
//traverse through the matrix for(int i=0; i
//print b.inorder(root);
}
// driver code int main() { int m[row][col] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {1, 0, 1, 0, 0}};
finduniquerows(m);
return 0; }
```
输出：
``` 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1
```
-
复杂度分析：
-
时间复杂度：
o(row x col row x log(row))。要遍历矩阵的时间复杂度为
o(row x col)，并将其插入 bst 的时间复杂度为每行o(log row)。 因此，总体时间复杂度为o(row x col row x log(row))。 -
辅助空间：
o(row)。需要存储 bst
o(row)空间。
-
方法 3：此方法使用 解决上述问题。 trie 是一种有效的信息检索数据结构。 使用 trie，可以使搜索复杂度达到最佳极限（键长度）。 如果我们将键存储在二分搜索树中，那么均衡的 bst 将需要与m * log n成比例的时间，其中m是最大字符串长度，n是树中键的数量。 使用 trie，我们可以搜索o(m)时间的键。 但是，代价取决于 trie 的存储要求。
注意：如果列数很大，此方法将导致整数溢出。
-
方法：
由于矩阵是布尔型，因此可以使用 trie 数据结构的变体，其中每个节点将有两个子代，一个为 0，另一个为 1。在 trie 中插入每一行。 如果该行已经存在，请不要打印该行。 如果该行不在 trie 中，请将其插入 trie 并打印。
-
算法：
-
创建可以存储行的 trie。
-
遍历矩阵并将行插入到 trie 中。
-
trie 无法存储重复项，因此重复项将被删除。
-
遍历 trie 并打印行。
-
-
实现：
c
```
// given a binary matrix of m x n of integers, // you need to return only unique rows of binary array
using namespace std;
// a trie node class node { public: bool isendofcol; node *child[2]; // only two children needed for 0 and 1 } ;
// a utility function to allocate memory // for a new trie node node newnode() { node temp = new node(); temp->isendofcol = 0; temp->child[0] = temp->child[1] = null; return temp; }
// inserts a new matrix row to trie. // if row is already present, // then returns 0, otherwise insets the row and // return 1 bool insert(node root, int (m)[col], int row, int col ) { // base case if (root == null) *root = newnode();
// recur if there are more entries in this row if (col < col) return insert (&((*root)->child[m[row][col]]), m, row, col 1);
else // if all entries of this row are processed { // unique row found, return 1 if (!((root)->isendofcol)) return (root)->isendofcol = 1;
// duplicate row found, return 0 return 0; } }
// a utility function to print a row void printrow(int(*m)[col], int row) { int i; for(i = 0; i < col; i) cout << m[row][i] << " "; cout << endl; }
// the main function that prints // all unique rows in a given matrix. void finduniquerows(int (m)[col]) { node root = null; // create an empty trie int i;
// iterate through all rows for (i = 0; i < row; i)
// insert row to trie if (insert(&root, m, i, 0))
// unique row found, print it printrow(m, i); }
// driver code int main() { int m[row][col] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {1, 0, 1, 0, 0}};
finduniquerows(m);
return 0; }
// this code is contributed by rathbhupendra
```
c
```
//given a binary matrix of m x n of integers, you need to return only unique rows of binary array
// a trie node typedef struct node { bool isendofcol; struct node *child[2]; // only two children needed for 0 and 1 } node;
// a utility function to allocate memory for a new trie node node newnode() { node temp = (node *)malloc( sizeof( node ) ); temp->isendofcol = 0; temp->child[0] = temp->child[1] = null; return temp; }
// inserts a new matrix row to trie. if row is already // present, then returns 0, otherwise insets the row and // return 1 bool insert( node root, int (m)[col], int row, int col ) { // base case if ( root == null ) *root = newnode();
// recur if there are more entries in this row if ( col < col ) return insert ( &( (*root)->child[ m[row][col] ] ), m, row, col 1 );
else // if all entries of this row are processed { // unique row found, return 1 if ( !( (root)->isendofcol ) ) return (root)->isendofcol = 1;
// duplicate row found, return 0 return 0; } }
// a utility function to print a row void printrow( int (*m)[col], int row ) { int i; for( i = 0; i < col; i ) printf( "%d ", m[row][i] ); printf("\n"); }
// the main function that prints all unique rows in a // given matrix. void finduniquerows( int (m)[col] ) { node root = null; // create an empty trie int i;
// iterate through all rows for ( i = 0; i < row; i ) // insert row to trie if ( insert(&root, m, i, 0) ) // unique row found, print it printrow( m, i ); }
// driver program to test above functions int main() { int m[row][col] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {1, 0, 1, 0, 0} };
finduniquerows( m );
return 0; }
```
输出：
``` 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0
```
-
复杂度分析：
-
时间复杂度：
o(row x col)。要遍历矩阵并在树中插入，时间复杂度为
o(row x col)。 该方法具有更好的时间复杂度。 同样，在打印时可以保持行的相对顺序，但会占用空间。 -
辅助空间：
o(row x col)。需要存储 trie
o(row x col)空间复杂度。
-
方法 4：此方法使用解决上述问题。 hashset类实现set接口，该接口由实际上是hashmap实例的哈希表支持。 不能保证集合的迭代顺序，这意味着该类不能保证元素随时间的恒定顺序。 此类允许使用null元素。 该类为基本操作（如添加，删除，包含和大小）提供恒定的时间性能，并假设哈希函数将元素正确分散在存储桶中。
-
方法：在此方法中，将整个行转换为单个字符串，然后检查是否在
hashset中已经存在该行。 如果存在该行，则将其保留，否则将打印唯一行并将其添加到hashset中。 -
算法：
-
创建一个
hashset，其中行可以存储为字符串。 -
遍历矩阵并将该行作为字符串插入
hashset中。 -
hashset无法存储重复项，因此重复项将被删除。 -
遍历
hashset并打印行。
-
-
实现：
c/c
```
// c code to print unique row in a // given binary matrix
using namespace std;
void printarray(int arr[][5], int row, int col) { unordered_set uset;
for(int i = 0; i < row; i ) { string s = "";
for(int j = 0; j < col; j ) s = to_string(arr[i][j]);
if(uset.count(s) == 0) { uset.insert(s); cout << s << endl;
} } }
// driver code int main() { int arr[][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {1, 1, 1, 0, 0}};
printarray(arr, 4, 5); }
// this code is contributed by // rathbhupendra
```
java
```
// java code to print unique row in a // given binary matrix import java.util.hashset;
public class gfg {
public static void printarray(int arr[][], int row,int col) {
hashset set = new hashset();
for(int i = 0; i < row; i ) { string s = "";
for(int j = 0; j < col; j ) s = string.valueof(arr[i][j]);
if(!set.contains(s)) { set.add(s); system.out.println(s);
} } }
// driver code public static void main(string[] args) {
int arr[][] = { {0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {1, 1, 1, 0, 0} };
printarray(arr, 4, 5); } }
```
python3
```
def printarray(matrix):
rowcount = len(matrix) if rowcount == 0: return
columncount = len(matrix[0]) if columncount == 0: return
row_output_format = " ".join(["%s"] * columncount)
printed = {}
for row in matrix: routput = row_output_format % tuple(row) if routput not in printed: printed[routput] = true print(routput)
mat = [[0, 1, 0, 0, 1], [1, 0, 1, 1, 0], [0, 1, 0, 0, 1], [1, 1, 1, 0, 0]]
printarray(mat)
```
c#
```
using system; using system.collections.generic;
// c# code to print unique row in a // given binary matrix
public class gfg {
public static void printarray(int[][] arr, int row, int col) {
hashset set = new hashset();
for (int i = 0; i < row; i ) { string s = "";
for (int j = 0; j < col; j ) { s = arr[i][j].tostring(); }
if (!set.contains(s)) { set.add(s); console.writeline(s);
} } }
// driver code public static void main(string[] args) {
int[][] arr = new int[][] { new int[] {0, 1, 0, 0, 1}, new int[] {1, 0, 1, 1, 0}, new int[] {0, 1, 0, 0, 1}, new int[] {1, 1, 1, 0, 0} };
printarray(arr, 4, 5); } }
// this code is contributed by shrikant13
```
输出：
``` 01001 10110 11100
```
-
复杂度分析：
-
时间复杂度：
o(row x col)。要遍历矩阵并将其插入
hashset中，时间复杂度为o(row x col)。 -
辅助空间：
o(row x col)。要存储
hashset，需要o(row x col)空间复杂度。
-
-
谢谢 anshuman kaushik 提出了这种方法。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
