算法通关村第十五关—用4KB内存寻找重复元素(青铜)

  用4KB内存寻找重复元素

用4KB内存寻找重复元素

 题目要求：给定一个数组，包含从1到N的整数，N最大为32000，数组可能还有重复值，且N的取值不定，若只有4KB的内存可用，该如何打印数组中所有重复元素。
 分析：本身是一道海量数据问题的热身题，如果去掉“只有4KB”的要求，我们可以先创建一个大小为N的数组，然后将这些数据放进来，但是这里数组最大为32KB,而题目有4KB的内存限制，我们就必须先确定该如何存放这个数组。
 如果只有4KB的空间，那么只能寻址842^10个比特，这个值比32000要大的，因此我们可以创建32000比特的位向量（比特数组），其中一个比特位置就代表一个整数。
 利用这个位向量，就可以遍历访问整个数组。如果发现数组元素是V,那么就将位置为V的设置为1，碰到重复元素，就输出一下。
 下面的代码仅供参考，你能看懂就行，不用自己会写，面试的时候也不可能让你构造一个4k的数组来测试

public class FindDuplicatesIn32000{public void checkDuplicates(int[]array){BitSet bs new BitSet(32000);for (int i=0;i<array.length;i++){int num array[i];int num = num -1;if (bs.get(num0)){System.out.println(num);}else{bs.set(num0);}}class BitSet{int[] bitset;public BitSet(int size){this.bitset new int[size >> 5];}boolean get(int pos){int wordNumber=(pos >> 5);//除以32int bitNumber=（pos & 0x1F);//取模32return (bitset [wordNumber](1 <bitNumber))!=0;}void set(int pos){int wordNumber=（pos >> 5);//除以32int bitNumber=（pos & 0x1F);//取模32bitset [wordNumber]=1 <bitNumber;}}
}