Kotlin程序员：高效判断数是否存在

【出自TX面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

在2.5亿个整数中判断一个数是否存在，注意，内存不足以容纳这2.5亿个整数。

分析与解答：

显然数据量太大，不可能一次性把所有的数据都加载到内存中，那么最容易想到的方法当然是分治法。

方法一：分治法(www.xing528.com)

对于大数据相关的算法题，分治法是一个非常好的方法。针对这道题而言，主要的思路为：可以根据实际可用内存的情况，确定一个Hash函数，比如hash（value）%1000，通过这个Hash函数可以把这2.5亿个数字划分到1000个文件中（a1，a2，…，a1000），然后再对待查找的数字使用相同的Hash函数求出Hash值，假设计算出的Hash值为i，如果这个数存在，那么它一定在文件ai中。通过这种方法就可以把题目的问题转换为文件ai中是否存在这个数。那么在接下来的求解过程中可以选用的思路比较多，如下所示：

（1）由于划分后的文件比较小了可以直接被装载到内存中，可以把文件中所有的数字都保存到hash_set中，然后判断待查找的数字是否存在。

（2）如果这个文件中的数字占用的空间还是太大，那么可以用相同的方法把这个文件继续划分为更小的文件，然后确定待查找的数字可能存在的文件，然后在相应的文件中继续查找。

方法二：位图法

对于这类判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。这里以32位整型为例，它可以表示数字的个数为2^32。可以申请一个位图，让每个整数对应位图中的一个bit，这样2^32个数需要位图的大小为512MB。具体实现的思路是：申请一个512M大小的位图，并把所有的位都初始化为0；接着遍历所有的整数，对遍历到的数字，把相应位置上的bit设置为1。最后判断待查找的数对应的位图上的值是多少，如果是0则表示这个数字不存在，如果是1则表示这个数字存在。