我们有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}
输出结果
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; }
输出结果
2 11