给定包含4300000000个32位整数的顺序文件，如何找到一个出现失少两次的整数

给定包含4300000000个32位整数的顺序文件,如何找出一个出现至少两次的整数？

一、位向量法

思路：考虑两个条件

1. 所有的整数都存储在顺序文件中，因此，读取文件的次数将明显影响算法的效率

2. 顺序文件中包含的整数个数为4300000000，如果全部读取放在内存中的话，必须要考虑内存空间因素。

 

解决方案：

由上面的问题，我们想到了Bit-Map，可以申请537500000个char型数组，数组中每个位对应4300000000个整数中的一个数，刚开始时，都所有的位都置0，如果有存在相对应的数，那么对应的位就置一。

问题又出来了，如何才能表示至少包含两次的整数呢？

这是，我们发现，要表示至少包含两次的整数，仅用一位来表示是不够的。那么用两位呢？00表示没有数据，01表示存在一个，10表示存在两个，11表示存在两个以上。

 

我们需要申请大小为1075000000的char类型的数组，两位对应一个数。

初始时，所有位都置零，然后开始读取顺序文件，读到整数后，相应的位做相应的改变。

这样，我们便只需要一次操作，而且使用了最少的内存便解决这个问题啦。

二、二分查找法

搜索范围从所有的32位正整数开始（全部当成unsigned int，简化问题），即[0, 2^32)，中间值即为2^31。然后遍历文件，如果小于2^31的整数个数大于N/2=2^31，则调整搜索范围为[0, 2^31]，反之亦然；然后再对整个文件再遍历一遍，直到得到最后的结果。T(n) = T(n/2) + n，总体的复杂度为o(logn)