给我一个面试题：
假设有一个包含40亿个整数的输入文件，请提供一种算法，生成一个不包含在文件中的整数。假设你有1 GB内存。如果只有10 MB内存，你会怎么做？
我的分析：
文件的大小为4×109×4字节=16 GB。
我们可以进行外部排序，这样可以让我们知道整数的范围。
我的问题是：在排序后的大整数集中检测缺失的整数的最佳方法是什么？
我的理解（阅读所有答案后）:
假设我们讨论的是32位整数，则有232= 40亿个不同的整数。
情况1：我们有1 GB = 109 * 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 * 106 * 8位 = 8000万个比特位
解决方案:
对于所有可能的16位前缀，有216个整数=65536，我们需要216 * 4 * 8 = 200万个比特位。我们需要构建65536个桶。对于每个桶，我们需要4个字节来保存所有可能性，因为最坏的情况是所有40亿个整数属于同一个桶。
- 通过第一次文件遍历，建立每个桶的计数器。
- 扫描桶，找到第一个少于65536个命中的桶。
- 通过文件的第二次遍历，构建新的桶，其高16位前缀与步骤2中发现的相同。
- 扫描步骤3中构建的桶，找到第一个没有命中的桶。
代码与上面的代码非常相似。
结论： 通过增加文件遍历次数来减少内存使用。
针对晚来者的澄清：问题在提问时没有明确说明文件中只有一个整数没有出现。至少大多数人不是这样理解的。评论线程中的许多评论都涉及该任务的变体。不幸的是，介绍这个变体的评论后来被其作者删除了，所以现在看起来像是它的孤儿回复误解了一切。非常抱歉，这很令人困惑。
int getMissingNumber(File inputFile) { return 4; }（参考资料：http://xkcd.com/221/） - johnny