在C ++中使用位数组查找数组的重复项

Z时代
2024-01-10
分类：综合

概念

我们有n个数字组成的数组，其中n最多为32,000。现在，给定的数组可能具有重复的条目，并且我们不知道n是什么。现在出现的问题是，只有4 KB的可用内存，如何显示或打印数组中所有重复的元素？

输入值

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

输出结果

2 11

2 and 11 appear more than once in given array.

输入值

arr[] = {60, 50, 60}

输出结果

方法

现在我们有4 KB的内存，表示我们可以寻址多达8 * 4 * 210位。应该注意，32 * 210位大于32000。因此我们可以生成一个32000位的位，其中每个位代表一个整数。

再次需要注意的是，如果我们需要生成一个32000位以上的位，那么我们可以轻松生成32000以上的位。实现此位向量，我们可以通过将位v设置为1来遍历数组，标记每个元素v。在这种情况下，当遍历重复元素时，我们将其打印出来。

示例

// 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整数（假设存储了
      //使用32位）
      arr1 = new int[(n1 >> 5) + 1];
   }
   //现在在给定位置获取一点值
   bool get(int pos1){
      //位置
      //整数。
      int index1 = (pos1 >> 5);
      //位数
      int bitNo1 = (pos1 & 0x1F);
      //确定给定位数的值
      //arr1 [index1]
      return (arr1[index1] & (1 << bitNo1)) != 0;
   }
   //用于在给定位置设置一点
   void set(int pos1){
      //确定位的位置索引
      int index1 = (pos1 >> 5);
      // Used to set bit number inarr1 [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;
}