低智儿童求教二分算法问题——编程珠玑 第二章问题A

lxyscls

问题是：

1个顺序文件（支持顺序读写）中有40亿个随机32位数（2的32方 4294967296），里面至少缺少一个数，请把这个数找出来

答案是（条件为可以使用几个稀疏顺序文件，只有几百字节大小内存）

依次读入文件，根据数字的最末尾 0 或者 1将其分割成两个文件，后面方法类推——倒数第二位0 或者 1再分割

===========

关于这个答案我真心看不懂嘛意思哇

假设只缺少一个数，OK，那么分开的两个文件必然有一个文件的数字数目不对，再对该文件进行二分查找，这样的查找次数应该是log2 N

但是假如不只少一个数，请问是不是对分开的文件如果数字数目不对（N/2），就需要对文件做二分查找

bruceteen

数是否有重复？一般没有标明不重复限定的，则不能假定其不重复。

看不懂什么叫“里面至少缺少一个数”？
“2的32方 4294967296” - “40亿个” = 294967296个，所以里面至少缺少294967296个数，而不是“里面至少缺少一个数”。如果限定为数不重复，那么就是里面缺少294967296个数（没有“至少”）

bruceteen

看原题：http://hi.baidu.com/renzherl/blo ... 68bddda78669ae.html
答案中很狗屎

1。“大约所需要40 0000 0000/8Byte=500MB的内存”
因为不知道缺失哪些数，所以是 4294967296/8Byte = 512MB的内存

2。 “读取n=40亿个整数，第1个bit为0或为1的放到不同的文件中（每个至多为n/2亿）”
第1个bit为0的32bits数一共有 21.47亿个，所以文件中至多需要保存 min(n,21.47亿) 个32bits整数，而不是 n/2亿个整数

3。使用所谓的“0-1二分查找”，单个文件大小需要 2^32/2*4字节，即 8G 大小的文件，而所谓的“位向量表示法”只需要 512M，而且代码复杂度和运行效率上也是差距很大

4。但作者一句瞎话“不过要一次性将所有数都映射到内存中”就把她打死了

bruceteen

看完了这个帖子 http://www.iteye.com/topic/1050323，整整十四页，没有答案

lxyscls

这个...难道是翻译问题？真心看不懂哇...

位图确实方便，一次性读入，不过需要500MB左右的内存

关键是这个题目太模糊了——40亿个数，明明2 ^ 32比40亿大黑多{:3_188:}