資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學使用 C++ 查詢二進位制矩陣中的重複行
假設我們有一個二進位制矩陣。接下來我們將介紹如何在這類矩陣中查詢重複行。假設該矩陣如下所示 −
| 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 |
在第 3、4、5 個位置有重複行。
為了解決這個問題，我們將使用 Trie 樹。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
更新於: 2020 年 1 月 3 日
129 次瀏覽
廣告