一道编程珠玑的题,终于搞懂了

给定一个包含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为重复出现的整数。

    改进:上面的办法有很多的冗余。于是提出了一个办法:建立一个新的文件(是顺序文件就可以)。在一次遍历过后,确定搜索的范围后,把原有文件里这个范围内的整数写到新的文件里去,下次搜索就只要搜索这个新文件了。这样可以得到近似线性的复杂度(但是常数项应该很大)。

    嗯,算法还要加强,不然以后面试要挂了,呵呵。

Leave a Reply

Your email address will not be published.