2 neqrhk NeQrhk 于 2016.01.19 21:01 提问

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

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

3个回答

caozhy
caozhy   Ds   Rxr 2016.01.19 21:08

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

caozhy
caozhy   Ds   Rxr 2016.01.19 21:09

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

91program
91program   Ds   Rxr 2016.01.19 21:09
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!