给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数。

(在文件中至少缺失一个这样的数为什么?)括号里的话怎么得到的
在具有足够内存的情况下,如何解决该问题?
如果有几个外部的临时文件可以用,但是只有几百字节的内存,又该如何解决该问题。

足够内存,用位图法。定义一个arr[4294967296]大小的数组,遍历顺序文件,遇到一个值,就把对应下标的置1,最后遍历这个数组,找0的元素。

如果只有几百的内存,可以用hashtable。不过位图只需要512M内存就可以了。

给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数。