算法通关村——位运算在查找重复元素中的妙用

用4KB内存寻找重复元素

给定一个数组，包含从1到N的整数，N最大为32000，数组可能还有重复值，且N的取值不定，若只有4KB的内存可用，该如何打印数组中所有重复元素。

如果不要求使用4KB，最简单就是使用N长的数组然后将元素都存入数组，再打印，但是题目规定了4KB，很显然这种做法就不大行了，一定会超出时间限制。

4KB=4 * 8 * 2 ^ 10 比特，这个值是大于32000，可以使用比特数组来存储相应的元素。利用这个位向量，就可以遍历访问整个数组。如果发现数组元素是v，那么就将位置为v的设置为1，碰到重复元素，就输出。代码就没什么可说的，真要实现起来，还是有一点复杂的。

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 num0 = 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;}}
}