一道编程珠玑的题，终于搞懂了
给定一个包含4300000000个32位整数的顺序文件，请问如何找到一个至少出现两次的整数？
顺序文件，不允许随机访问。
解答：Binary Search，但不是对文件内容折半，而是对搜索范围折半。由于4.3G>32位的整数空间，根据鸽笼原理，肯定会有重复的整数。搜索范围从所有的32位正整数开始（全部当成unsigned int，简化问题），即[0, 2^32)，中间值即为2^31。然后遍历文件，如果小于2^31的整数个数大于2^31，则调整搜索范围为[0, 2^31]，反之亦然；然后再对整个文件再遍历一遍，直到得到最后的结果。这样一共会有logn次的搜索，每次过n个整数（每次都是完全遍历），总体的复杂度为o(nlogn)。
例子：数组[4,2,5,1,3,6,3,7,0,7]，假定从3位的整数空间内搜索。第一次的范围为[0,8)，遍历过后发现[0,4)范围内的整数个数为5，于是调整为搜索[0,4)范围内的整数。第二次发现[2, 4)范围内的证书为3，大于2，于是调整为[2, 4)。再经过第三次的遍历，找出3为重复出现的整数。
改进：上面的办法有很多的冗余。于是提出了一个办法：建立一个新的文件（是顺序文件就可以）。在一次遍历过后，确定搜索的范围后，把原有文件里这个范围内的整数写到新的文件里去，下次搜索就只要搜索这个新文件了。这样可以得到近似线性的复杂度（但是常数项应该很大）。
嗯，算法还要加强，不然以后面试要挂了，呵呵。
近期评论