查找内存有限的重复元素

Question

以下是 Cracking the coding interview 中的一个问题：

您有一个包含从 1 到 N 的所有数字的数组，其中 N 最多为 32,000。数组可能有重复的条目，而您不知道 N 是什么。只有 4KB 的内存可用，您将如何打印数组中的所有重复元素？

方法签名是

public static void checkDuplicates(int[] array)

然后解决方案解释了如何使用位向量通过将每个整数表示为一个位来解决这个问题。我的困惑是当我们运行这个方法时，它不会在内存中加载整个数组来循环遍历它吗？现在，如果array大小说，例如，10 亿（许多重复元素）该程序不会失败，因为它将整个数组加载到内存中，而我们拥有的内存是32 * 2^10位？

Answer 1

下面是经过测试的代码：

public void checkDuplicates(int[] nums){
    int bytesNeeded = (nums.length/8) + 1;
    byte[] bitSet = new byte[bytesNeeded];

    for(int i=0; i<nums.length; i++){
        int n = nums[i];
        int byteIndex = n / 8;
        int indexInByte = n % 8;

        byte bit = (byte)(bitSet[byteIndex] & (1 << indexInByte));
        if(bit > 0){
            System.out.print(nums[i] + " ");
        }else{
            bitSet[byteIndex] |= 1 << indexInByte; 
        }
    }
}