在給定的布爾矩陣中打印唯一行 · GeeksForGeeks 中文系列教程

# 在給定的布爾矩陣中打印唯一行 > 原文： [https://www.geeksforgeeks.org/print-unique-rows/](https://www.geeksforgeeks.org/print-unique-rows/) 給定一個二進制矩陣，打印給定矩陣的所有唯一行。 **示例**： ``` 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** ：此方法說明解決上述問題的簡單方法。 * **方法**：一種簡單的方法是使用所有已處理的行檢查每一行。打印第一行。現在，從第二行開始，針對每一行，將該行與已處理的行進行比較。如果該行與任何已處理的行匹配，請跳過該行，否則將其打印出來。 * **算法**： 1. 遍歷矩陣行 2. 對于每一行，檢查是否有比當前索引少的相似行。 3. 如果任何兩行相似，則不要打印該行。 4. 否則打印該行。 * **Implementation:** ``` // Given a binary matrix of M X N of integers,? // you need to return only unique rows of binary array? #include <bits/stdc++.h> using namespace std; #define ROW 4? #define COL 5? // 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<ROW; i++) ????{ ????????int flag=0; ????????//check if there is similar column ????????//is already printed, i.e if i and? ????????//jth column match. ????????for(int j=0; j<i; j++) ????????{ ????????????flag=1; ????????????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<COL; j++) ????????????????cout<<M[i][j]<<" "; ????????????cout<<endl; ????????} ????} } // 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** ：此方法使用[二分搜索樹](http://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/)解決上述操作。二分搜索樹是基于節點的二進制樹數據結構，具有以下屬性： * 節點的左子樹僅包含鍵號小于節點鍵號的節點。 * 節點的右子樹僅包含鍵大于該節點的鍵的節點。 * 左和右子樹也都必須是二叉搜索樹。 * 不得有重復的節點。二分搜索樹的上述屬性提供了鍵之間的順序，因此可以快速完成搜索，最小和最大等操作。如果沒有順序，那么我們可能必須比較每個鍵以搜索給定的鍵。 * **方法**：該過程必須從找到每行的十進制等效項并將它們插入 BST 開始。眾所周知，BST 的每個節點將包含兩個字段，一個字段用于十進制值，另一字段用于行號。如果節點重復，則不得插入該節點。最后，遍歷 BST 并打印相應的行。 * **算法**： 1. 創建一個 BST，在其中不能存儲任何重復的元素。創建一個函數以將行轉換為十進制，并將十進制值轉換為二進制數組。 2. 遍歷矩陣并將該行插入 BST。 3. 遍歷 BST（有序遍歷）并將十進制轉換為二進制數組并打印。 * **Implementation:** ``` // Given a binary matrix of M X N of integers,? // you need to return only unique rows of binary array? #include <bits/stdc++.h> using namespace std; #define ROW 4? #define COL 5? 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<COL; i++) ????{ ????????sum+=pow(2,i)*arr[i]; ????} ????return sum; } //print the column represented as integers void print(int p) { ????for(int i=0; i<COL; i++) ????{ ????????cout<<p%2<<" "; ????????p/=2; ????} ????cout<<endl; } // 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<ROW; i++) ????{ ????????//insert the row into BST ????????root=b.Insert(root,convert(M[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 數據結構](https://www.geeksforgeeks.org/trie-insert-and-search/)解決上述問題。 Trie 是一種有效的信息檢索數據結構。使用 Trie，可以使搜索復雜度達到最佳極限（密鑰長度）。如果我們將密鑰存儲在二分搜索樹中，那么均衡的 BST 將需要與 M * log N 成比例的時間，其中 M 是最大字符串長度，N 是樹中密鑰的數量。使用 Trie，我們可以搜索 O（M）時間的密鑰。但是，罰款取決于 Trie 的存儲要求。 **注意**：如果列數很大，此方法將導致整數溢出。 * **方法**：由于矩陣是布爾型，因此可以使用 Trie 數據結構的變體，其中每個節點將有兩個子代，一個為 0，另一個為 1。在 Trie 中插入每一行。如果該行已經存在，請不要打印該行。如果該行不在 Trie 中，請將其插入 Trie 并打印。 * **算法**： 1. 創建可以存儲行的 Trie。 2. 遍歷矩陣并將行插入到 Trie 中。 3. Trie 無法存儲重復項，因此重復項將被刪除 4. 遍歷 Trie 并打印行。 * **實現**： ## C++ ``` // Given a binary matrix of M X N of integers,? // you need to return only unique rows of binary array? #include <bits/stdc++.h> using namespace std; #define ROW 4? #define COL 5? // 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 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define ROW 4 #define COL 5 // 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 數據結構](https://www.geeksforgeeks.org/hashset-in-java/)解決上述問題。 HashSet 類實現 Set 接口，該接口由實際上是 HashMap 實例的哈希表支持。不能保證集合的迭代順序，這意味著該類不能保證元素隨時間的恒定順序。此類允許使用 null 元素。該類為基本操作（如添加，刪除，包含和大小）提供恒定的時間性能，并假設哈希函數將元素正確分散在存儲桶中。 * **方法**：在此方法中，將整個行轉換為單個 String，然后檢查是否在 HashSet 中已經存在該行。如果存在該行，則將其保留，否則將打印唯一行并將其添加到 HashSet 中。 * **算法**： 1. 創建一個 HashSet，其中行可以存儲為 String。 2. 遍歷矩陣并將該行作為 String 插入 HashSet 中。 3. HashSet 無法存儲重復項，因此重復項將被刪除 4. 遍歷 HashSet 并打印行。 * **實現**： ## C/C++ ``` // C++ code to print unique row in a? // given binary matrix? #include<bits/stdc++.h>? using namespace std;? void printArray(int arr[][5], int row,? ??????????????????????????????int col)? {? ????unordered_set<string> 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<String> set = new HashSet<String>(); ????????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 ``` # Python3 code to print unique row in a? # given binary matrix 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) # Driver Code mat = [[0, 1, 0, 0, 1],? ???????[1, 0, 1, 1, 0],? ???????[0, 1, 0, 0, 1], ???????[1, 1, 1, 0, 0]] printArray(mat) # This code is contributed by myronwalker ``` ## 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<string> set = new HashSet<string>(); ????????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）。要存儲 HashSet O（ROW x COL），需要空間復雜度。 * *謝謝 Anshuman Kaushik 提出了這種方法。*