Tìm các hàng trùng lặp trong ma trận nhị phân trong C ++

Giả sử chúng ta là một ma trận nhị phân. Ở đây chúng ta sẽ xem cách tìm các hàng trùng lặp trong ma trận đó. Giả sử ma trận giống như -

Có các hàng trùng lặp ở vị trí 3, 4, 5.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng Trie. Trie là một cấu trúc dữ liệu hiệu quả được sử dụng để truy xuất dữ liệu mạnh mẽ trong đó tập ký tự nhỏ. Độ phức tạp tìm kiếm là tối ưu như độ dài khóa. Vì vậy, lúc đầu chúng ta sẽ chèn trie nhị phân. Nếu hàng mới được thêm vào đã có thì hàng đó sẽ trùng lặp.

Ví dụ

#include<iostream>
using namespace std;
const int MAX = 100;
class Trie {
   public:
   bool leaf_node;
   Trie* children[2];
};
Trie* getNode() {
   Trie* node = new Trie;
   node->children[0] = node->children[1] = NULL;
   node->leaf_node = false;
   return node;
}
bool insert(Trie*& head, bool* arr, int N) {
   Trie* curr = head;
   for (int i = 0; i < N; i++) {
      if (curr->children[arr[i]] == NULL)
      curr->children[arr[i]] = getNode();
      curr = curr->children[arr[i]];
   }
   if (curr->leaf_node)
   return false;
   return (curr->leaf_node = true);
}
void displayDuplicateRows(bool matrix[][MAX], int M, int N) {
   Trie* head = getNode();
   for (int i = 0; i < M; i++)
   if (!insert(head, matrix[i], N))
   cout << "There is a duplicate row at position: "<< i << endl;
}
int main() {
   bool mat[][MAX] = {
      {1, 1, 0, 1, 0, 1},
      {0, 0, 1, 0, 0, 1},
      {1, 0, 1, 1, 0, 0},
      {1, 1, 0, 1, 0, 1},
      {0, 0, 1, 0, 0, 1},
      {0, 0, 1, 0, 0, 1},
   };
   displayDuplicateRows(mat, 6, 6);
}

Đầu ra

There is a duplicate row at position: 3
There is a duplicate row at position: 4
There is a duplicate row at position: 5