bbb*_*bbb 13 algorithm programming-pearls
我似乎无法理解这是如何工作的.
问题:
给定一个顺序文件,其中包含最多40个随机顺序的32位整数,找到一个不在文件中的32位整数(并且必须至少有一个缺失)
答:
根据代表每个整数的32位来查看这个二进制搜索是有帮助的.在算法的第一遍中,我们读取(最多)40亿个输入整数,并将具有前导零位的那些写入一个顺序文件,将那些具有前导一位的那些写入另一个文件.
其中一个文件最多包含20亿个整数,因此我们接下来将该文件用作当前输入并重复探测过程,但这次是在第二位.
所以通过一遍又一遍地分割文件(二进制搜索),这实际上会导致我丢失32位整数？
WuH*_*ted 12
每次通过后,您的下一个通行证将在您编译的两个列表中较小的一个上.
在某些时候,你必须遇到一个空列表,这将决定你的号码.例如,我们只使用3位数.
000
001
110
100
111
我们有第一次通过后
000
001
110
100
111
然后我们查看第一个列表中的第2位,因为它小于(或等于)第二个位.我们会将它们拆分成
000
001
empty list
注意开始的文件是如何01为空,这意味着没有以01这样开头010且011缺少的数字.
我们最终必须有一个缺失列表的原因是因为我们每次都为下一次传递选择较小的列表.