我收到了这个面试问题：

给定一个具有 40 亿个整数的输入文件，提供一个算法来生成一个不包含在文件中的整数。假设您有 1 GB 内存。如果您只有 10 MB
的内存，请跟进您会做什么。

我的分析：

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

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

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

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

假设我们谈论的是 32 位整数，则有 2 32 = 4*10 9 个不同的整数。

案例 1：我们有 1|GB = 1 * 10 9 * 8 bits = 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：10MB内存=10 * 10 6 * 8 bits = 80,000,000 bits

解决方案：

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

1. 通过文件的第一次遍历构建每个桶的计数器。
2. 扫描桶，找到第一个命中少于 65536 的桶。
3. 构建新的存储桶，其高 16 位前缀是我们在第 2 步到文件的第二遍中找到的
4. 扫描step3构建的bucket，找到第一个没有命中的bucket。
   

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

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

对迟到的人的澄清：问题，正如所问的，并不是说文件中没有确切的一个整数——至少大多数人不是这样解释的。不过，评论线程中的许多评论 都是
关于该任务的变体。不幸的是，将其 引入 评论线程的评论后来被其作者删除，所以现在看起来对它的孤立回复只是误解了一切。非常混乱，抱歉。