在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
方法
现在我们有4KB的内存，表示我们可以寻址多达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;
}输出结果
2 11