在C ++中以二进制矩阵查找重复的行
假设我们有一个二进制矩阵。在这里，我们将看到如何在该矩阵中查找重复的行。假设矩阵像-
在位置3、4、5处有重复的行。
为了解决这个问题，我们将使用Trie。Trie是一种高效的数据结构，用于在字符集较小的情况下增强和检索数据。搜索复杂度是最佳的密钥长度。因此，首先我们将插入二进制特里。如果已经存在新添加的行，则该行是重复的。
示例
#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);
}输出结果
There is a duplicate row at position: 3 There is a duplicate row at position: 4 There is a duplicate row at position: 5
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短