C++에서 비트 배열을 사용하여 배열의 중복 찾기

컨셉

n개의 숫자 배열이 있습니다. 여기서 n은 최대 32,000입니다. 이제 주어진 배열에 중복 항목이 있을 수 있으며 n이 무엇인지 모릅니다. 이제 사용 가능한 메모리가 4KB뿐인 경우 배열의 모든 중복 요소를 표시하거나 인쇄하는 방법에 대한 질문이 발생합니다.

입력

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

출력

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

입력

arr[] = {60, 50, 60}

출력

60

방법

이제 최대 8 * 4 * 210비트의 주소를 지정할 수 있음을 나타내는 4KB의 메모리가 있습니다. 32 * 210비트는 32000보다 큽니다. 따라서 각 비트는 하나의 정수를 나타내는 32000비트로 비트를 생성할 수 있습니다. .

다시 한 번 32000비트보다 많은 비트를 생성해야 하는 경우 32000비트 이상을 쉽게 생성할 수 있다는 점에 유의해야 합니다. 이 비트 벡터를 구현하면 비트 v를 1로 설정하여 각 요소 v에 플래그를 지정하여 배열을 반복할 수 있습니다. 이 경우 중복 요소를 탐색할 때 인쇄합니다.

예시

// 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