我得到了这个面试问题：

给定一个具有40亿个整数的输入文件，请提供一种算法来生成文件中不包含的整数。假设您有1 GB的内存。如果只有10 MB的内存，请执行后续操作。

我的分析：

文件大小为4×10 9 ×4字节= 16 GB。

我们可以进行外部排序，从而让我们知道整数的范围。

我的问题是在已排序的大整数集中检测丢失的整数的最佳方法是什么？

我的理解（阅读所有答案之后）：

假设我们正在谈论32位整数，那么有2 32 = 4 * 10 9个不同的整数。

情况1：我们有1 GB = 1 * 10 9 * 8位= 80亿位内存。

解：

如果我们用一位代表一个不同的整数，那就足够了。我们不需要排序。

实现方式：

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

情况2：10 MB内存= 10 * 10 6 * 8位= 8000万位

解：

对于所有可能的16位前缀，有2 16个整数= 65536，我们需要2 16 * 4 * 8 =
2百万个位。我们需要构建65536个存储桶。对于每个存储桶，我们需要4个字节来保存所有可能性，因为最坏的情况是所有40亿个整数都属于同一个存储桶。

1. 通过第一次遍历文件来构建每个存储桶的计数器。
2. 扫描存储桶，找到命中率小于65536的第一个。
3. 通过在文件的第二遍中构建在步骤2中发现高16位前缀的新存储桶
4. 扫描步骤3中构建的存储桶，找到第一个没有命中的存储桶。
   

该代码与上面的代码非常相似。

结论：我们通过增加文件传递来减少内存。

对于迟到的人的澄清：问的问题不是说文件中没有正好包含一个整数-至少这不是大多数人的解释方式。不过，注释线程 中的 许多注释 都
与任务的变化有关。不幸的是， 将 其 引入
注释线程的注释后来被其作者删除了，因此现在看来，孤立的答复似乎误解了所有内容。非常令人困惑，对不起。