सी ++ में बिट सरणी का उपयोग करके सरणी के डुप्लिकेट खोजें

अवधारणा

हमारे पास n संख्याओं की एक सरणी है, जहाँ n अधिकतम 32,000 है। अब दिए गए सरणी में डुप्लिकेट प्रविष्टियाँ हो सकती हैं और हम नहीं जानते कि n क्या है। अब सवाल यह उठता है कि केवल 4 किलोबाइट मेमोरी उपलब्ध होने से, सरणी में सभी डुप्लिकेट तत्वों को कैसे प्रदर्शित या प्रिंट किया जाएगा?

इनपुट

arr[] = {2, 6, 2, 11, 13, 11}

आउटपुट

2 11
2 and 11 appear more than once in given array.

इनपुट

arr[] = {60, 50, 60}

आउटपुट

60

तरीके

अब हमारे पास 4 किलोबाइट मेमोरी है जो इंगित करती है कि हम 8 * 4 * 210 बिट्स को संबोधित कर सकते हैं। यह ध्यान दिया जाना चाहिए कि 32 * 210 बिट्स 32000 से बड़ा है। इसलिए हम 32000 बिट्स के साथ थोड़ा सा उत्पन्न कर सकते हैं, जहां प्रत्येक बिट एक पूर्णांक का प्रतिनिधित्व करता है ।

फिर से यह ध्यान दिया जाना चाहिए कि यदि हमें 32000 बिट्स से अधिक के साथ बिट उत्पन्न करने की आवश्यकता है तो हम 32000 से अधिक आसानी से और अधिक उत्पन्न कर सकते हैं; इस बिट वेक्टर को लागू करते हुए, हम सरणी के माध्यम से पुनरावृति करने में सक्षम हो सकते हैं, प्रत्येक तत्व v को बिट v को 1 पर सेट करके ध्वजांकित कर सकते हैं। इस मामले में, जब हम एक डुप्लिकेट तत्व को पार करते हैं, तो हम इसे प्रिंट करते हैं।

उदाहरण

// C++ program to print all Duplicates in array
#include <bits/stdc++.h>
using namespace std;
// Shows a class to represent an array of bits using
// array of integers
class BitArray{
   int *arr1;
   public:
   BitArray() {}
   // Constructor
   BitArray(int n1){
      // Used to divide by 32. To store n bits, we require
      // n/32 + 1 integers (Assuming int is stored
      // using 32 bits)
      arr1 = new int[(n1 >> 5) + 1];
   }
   // Now get value of a bit at given position
   bool get(int pos1){
      // Used to divide by 32 to find position of
      // integer.
      int index1 = (pos1 >> 5);
      // Now determine bit number in arr[index]
      int bitNo1 = (pos1 & 0x1F);
      // Determine value of given bit number in
      // arr1[index1]
      return (arr1[index1] & (1 << bitNo1)) != 0;
   }
   // Used to set a bit at given position
   void set(int pos1){
      // Determine index of bit position
      int index1 = (pos1 >> 5);
      // Used to set bit number in arr1[index1]
      int bitNo1 = (pos1 & 0x1F);
      arr1[index1] |= (1 << bitNo1);
   }
   //Shows main function to print all Duplicates
   void checkDuplicates1(int arr1[], int n1){
      // Used to create a bit with 32000 bits
      BitArray ba1 = BitArray(320000);
      // Used to traverse array elements
      for (int i = 0; i < n1; i++){
         // Shows index in bit array
         int num1 = arr1[i];
         // Now if num is already present in bit array
         if (ba1.get(num1))
            cout << num1 << " ";
         // Otherwise or else insert num
         else
            ba1.set(num1);
      }
   }
};
// Driver code
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