存有100万个<2^20正整数的文件中找到任意一个不在其中的数

Question

数字有重复，限制内存只能用几十个字节。未给定需要查找的数，只要找出任意一个即可

Answer 1

知乎链接：http://www.zhihu.com/question/29743992

由于2^20 = 1048576 > 1000000 所以必定存在不在数组中的元素。

1. 扫描所有数，统计最高位0 - 9数字的个数。
2. 再扫描一遍，把最高位数字最少（记为a_1）的整数存在另一个文件。

对所有新生成的文件重复上述算法，显然a_1a_2...即为所求。

时间复杂度 < 2*(n + n/10 + n/10^2 + ...) = O(n)，空间复杂度为O(1)（文件用的储存空间而非内存）。

P.S. 如果不允许使用文件，那么时间复杂度可以达到O(kn)。（k为整数位数）

这是在知乎上得到的答案，之前的回答都可以实现，但是感觉这个更好一些。完善一下改为：

第n次扫描
1. 扫描存储的文件，统计第n位（右往左数）0 - 9数字的个数b_n。
2. 再扫描一遍，把第n位数字最少（记为a_1）的整数存在另一个文件。
对所有新生成的文件重复上述算法，当b_n=0时结束，显然a_1a_2...a_n…即为所求。

Answer 2

查查布隆过滤器 bloomfilter 在搜索引擎中有广泛应用，有误报但是不会漏报，所以，不在其中的数一定至少有1 bit不为1，从而判定该数。

http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html

Answer 3

目测用bitmap，
但是内存小，所以明显不行，只能用硬盘空间换内存，
先逐行扫描这个文件，
根据扫描出来的数字的范围，将之插入文件里，
文件规律为：
每10个数字存进一个文件，
比如文件夹0，表示的范围为0-9，文件夹1表示的是10-19，文件夹n表示10n~10n-1,
如果扫描出的是1012，那么就是文件名为101的文件，如果该文件不存在就创建之，存在就添加进去，每行一个数字。
扫描完了后，就能得到一堆文件，
依次扫描这堆文件，读取里面的数字，如果数字的个数不为10，那么肯定是有缺的，找这个缺的很容易。
当然，一般操作系统对文件夹的个数是有限制的，所以呢，这个10万个文件可以划分3个层级存储，取模3次就行了。

因为你说是几十个字节的内存，也没说多少，我就选10为范围了，其实范围可以大点的。