अवधारणा
हमारे पास n संख्याओं की एक सरणी है, जहां n अधिकतम 32,000 है। अब दी गई सरणी में डुप्लिकेट प्रविष्टियां हो सकती हैं और हम नहीं जानते कि n क्या है। अब सवाल उठता है कि केवल 4 किलोबाइट्स मेमोरी उपलब्ध होने पर, सरणी में सभी डुप्लिकेट तत्वों को कैसे प्रदर्शित या प्रिंट करेंगे?
इनपुट
arr[] = {2, 6, 2, 11, 13, 11}आउटपुट
2 11 2 और 11 दी गई सरणी में एक से अधिक बार दिखाई देते हैं।
इनपुट
arr[] = {60, 50, 60}आउटपुट
60
विधियां
अब हमारे पास 4 किलोबाइट्स मेमोरी है जो इंगित करता है कि हम 8 * 4 * 2^10 बिट्स तक एड्रेस कर सकते हैं। यह ध्यान दिया जाना चाहिए कि 32 * 2^10 बिट्स 32000 से बड़ा है। तो हम 32000 बिट्स का एक बिट वेक्टर बना सकते हैं, जहां प्रत्येक बिट एक पूर्णांक को दर्शाता है।
फिर यह ध्यान दिया जाना चाहिए कि यदि हमें 32000 से अधिक बिट्स का बिट वेक्टर बनाने की आवश्यकता है तो हम इसे आसानी से 32000 से अधिक बना सकते हैं; इस बिट वेक्टर को लागू करके, हम सरणी के माध्यम से पुनरावृति करने में सक्षम हो सकते हैं, प्रत्येक तत्व v को बिट v को 1 पर सेट करके फ्लैग कर सकते हैं। इस मामले में, जब हम एक डुप्लिकेट तत्व पार करते हैं, तो हम इसे प्रिंट करते हैं।
उदाहरण
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// C++ program to print all Duplicates in array #include <bits/stdc++.h> using namespace std; // पूर्णांकों की सरणी का उपयोग करके बिट्स की सरणी को दर्शाने वाला क्लास class BitArray{ int *arr1; public: BitArray() {} // कंस्ट्रक्टर BitArray(int n1){ // 32 से विभाजित करने के लिए उपयोग किया जाता है। n बिट्स संग्रहीत करने के लिए, हमें // n/32 + 1 पूर्णांक चाहिए (यह मानते हुए कि int // 32 बिट्स का उपयोग करके संग्रहीत होता है) arr1 = new int[(n1 >> 5) + 1]; } // दी गई स्थिति पर बिट का मान प्राप्त करें bool get(int pos1){ // पूर्णांक की स्थिति खोजने के लिए 32 से विभाजित करें। int index1 = (pos1 >> 5); // अब arr[index] में बिट संख्या निर्धारित करें int bitNo1 = (pos1 & 0x1F); // arr1[index1] में दिए गए बिट संख्या का मान निर्धारित करें return (arr1[index1] & (1 << bitNo1)) != 0; } // दी गई स्थिति पर बिट सेट करने के लिए उपयोग किया जाता है void set(int pos1){ बिट स्थिति का इंडेक्स निर्धारित करें int index1 = (pos1 >> 5); // arr1[index1] में बिट संख्या सेट करने के लिए उपयोग किया जाता है int bitNo1 = (pos1 & 0x1F); arr1[index1] |= (1 << bitNo1); } // सभी डुप्लिकेट प्रिंट करने के लिए मुख्य फ़ंक्शन दिखाता है void checkDuplicates1(int arr1[], int n1){ // 32000 बिट्स का बिट वेक्टर बनाने के लिए उपयोग किया जाता है BitArray ba1 = BitArray(320000); // सरणी तत्वों को पार करने के लिए उपयोग किया जाता है for (int i = 0; i < n1; i++){ // बिट सरणी में इंडेक्स int num1 = arr1[i]; // अब यदि num पहले से ही बिट सरणी में मौजूद है if (ba1.get(num1)) cout << num1 << " "; // अन्यथा या फिर num डालें else ba1.set(num1); } } }; // ड्राइवर कोड int main(){ int arr1[] = {2, 6, 2, 11, 13, 11}; int n1 = sizeof(arr1) / sizeof(arr1[0]); BitArray obj1 = BitArray(); obj1.checkDuplicates1(arr1, n1); return 0; }आउटपुट
2 11
