अवधारणा
एक दिए गए m x m मैट्रिक्स के संबंध में, समस्या मैट्रिक्स की सभी पंक्तियों में सामान्य सभी विशिष्ट तत्वों को निर्धारित करना है। तो तत्वों को किसी भी क्रम में प्रदर्शित किया जा सकता है।
इनपुट
mat[][] = { {13, 2, 15, 4, 17}, {15, 3, 2, 4, 36}, {15, 2, 15, 4, 12}, {15, 26, 4, 3, 2}, {2, 19, 4, 22, 15} }आउटपुट
2 4 15
विधियां
पहली विधि: तीन नेस्टेड लूप्स लागू करें। सत्यापित करें कि पहली पंक्ति का एक तत्व सभी बाद की पंक्तियों में मौजूद है या नहीं। यहां, समय जटिलता O(m^3) है। डुप्लिकेट तत्वों को नियंत्रित करने के लिए अतिरिक्त स्थान की आवश्यकता हो सकती है।
दूसरी विधि: मैट्रिक्स की सभी पंक्तियों को व्यक्तिगत रूप से बढ़ते क्रम में व्यवस्थित या सॉर्ट करें। तो हम फिर 3 सॉर्टेड सरणियों में सामान्य तत्वों को खोजने की समस्या के संशोधित दृष्टिकोण को लागू करते हैं। उसी के लिए एक कार्यान्वयन नीचे दिया गया है।
उदाहरण
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// C++ implementation to find distinct elements // common to all rows of a matrix #include <bits/stdc++.h> using namespace std; const int MAX1 = 100; // प्रत्येक पंक्ति को व्यक्तिगत रूप से // बढ़ते क्रम में सॉर्ट करने वाला फ़ंक्शन void sortRows1(int mat1[][MAX1], int m){ for (int i=0; i<m; i++) sort(mat1[i], mat1[i] + m); } // सभी सामान्य तत्वों को खोजने वाला फ़ंक्शन void findAndPrintCommonElements1(int mat1[][MAX1], int m){ //पंक्तियों को व्यक्तिगत रूप से सॉर्ट करने के लिए उपयोग किया जाता है sortRows1(mat1, m); // प्रत्येक पंक्ति का वर्तमान कॉलम इंडेक्स संग्रहीत किया जाता है // जहां से उस पंक्ति में तत्व खोजा जा रहा है int curr_index1[m]; memset(curr_index1, 0, sizeof(curr_index1)); int f = 0; for (; curr_index1[0]<m; curr_index1[0]++){ // पहली पंक्ति के वर्तमान कॉलम इंडेक्स पर मौजूद मान इंगित करता है int value1 = mat1[0][curr_index1[0]]; bool present1 = true; //'value' को सभी बाद की पंक्तियों में खोजा जा रहा है इंगित करता है for (int i=1; i<m; i++){ // वर्तमान कॉलम इंडेक्स से उस पंक्ति के सभी तत्वों के माध्यम से पुनरावृति करने के लिए उपयोग किया जाता है // जब तक 'value' से बड़ा तत्व न मिले या पंक्ति का अंत न हो while (curr_index1[i] < m && mat1[i][curr_index1[i]] <= value1) curr_index1[i]++; // अब यदि तत्व पंक्ति के 'curr_index' से पहले कॉलम पर मौजूद नहीं था if (mat1[i][curr_index1[i]-1] != value1) present1 = false; // अब यदि पंक्ति के सभी तत्व // पार कर लिए गए हैं if (curr_index1[i] == m){ f = 1; break; } } // अब यदि 'value' सभी पंक्तियों में सामान्य है if (present1) cout << value1 << " "; // अब यदि किसी पंक्ति को पूरी तरह से पार कर लिया गया है // तो और सामान्य तत्व नहीं मिल सकते if (f == 1) break; } } // ऊपर का परीक्षण करने के लिए ड्राइवर प्रोग्राम int main(){ int mat1[][MAX1] = { {13, 2, 15, 4, 17},{15, 3, 2, 4, 36},{15, 2, 15, 4, 12}, {15, 26, 4, 3, 2},{2, 19, 4, 22, 15}}; int m = 5; findAndPrintCommonElements1(mat1, m); return 0; }आउटपुट
2 4 15
