मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। यहां हम देखेंगे कि उस मैट्रिक्स में डुप्लिकेट पंक्तियों को कैसे ढूंढें। मान लीजिए मैट्रिक्स इस तरह है -
| 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 पर डुप्लिकेट पंक्तियां हैं।
इसे हल करने के लिए, हम ट्राई का उपयोग करेंगे। ट्राई डेटा संग्रह और पुनर्प्राप्ति के लिए एक कुशल डेटा संरचना है जहां वर्ण समूह छोटा होता है। खोज जटिलता कुंजी लंबाई के रूप में इष्टतम होती है। तो पहले हम बाइनरी ट्राई डालेंगे। यदि नई जोड़ी गई पंक्ति पहले से मौजूद है, तो वह डुप्लिकेट है।
उदाहरण
#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
