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

处理海量数据的思路

1.使用位存储：占用的空间是存整数的 1/8 。

2.分块：也叫外部排序，将大文件划分为若干小块，先处理小块再逐步得到想要的结果，需要至少遍历两次全部序列，是用时间换空间的方法。

3.堆：极其适合超大数据或者流数据中找第 K 大，第 K 小， K 个最大， K 个最小等等问题。

用4KB内存寻找重复元素

给定一个数组，长度最大为32000 ，在其中找重复元素，但是只能使用 4KB 内存。

采用位运算。

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);
            int bitNumber = (pos & 0x1F);
            return (bitSet[wordNumber] & (1 << bitNumber)) != 0;
        }
        void set(int pos) {
            int wordNumber = (pos >> 5);
            int bitNumber = (pos & 0x1F);
            bitset[wordNumber] |= 1 << bitNumber;
        }
    }
}

如果对您有帮助，请点赞关注支持我，谢谢！ ?
如有错误或者不足之处，敬请指正！ ?
个人主页：星不易 ?
算法通关村专栏：不易|算法通关村 ?