如何在大量的数据中找出不重复的整数?

更新时间:2023年03月07日10时42分来源:传智教育浏览次数:

好口碑IT培训

　　·问题描述：

　　在2.5亿个整数中找出不重复的整数，注意，内存不足以容纳这2.5亿个整数。

　　·解题思路：

　　因为这道题目阐明无法一次把所有数据加载到内存中，因此我们可以采用分治法和位图法进行求解。

　　·方法一：分治法

　　利用Hash的方法，把这2.5亿个数划分到更小的文件中，以确保每个文件的大小超过可用的内存大小。接着针对每个小文件来说，所有的数据可以一次性被加载到内存中，因此可以使用字典或者set来找到每个小文件中不重复的数。当处理完所有的文件后就可以找出这2.5亿个整数中所有的不重复的数。

　　·方法二：位图法

　　对于整数相关算法的求解，位图法是一种非常实用的算法。对于本题来说，如果可用的内存空间超过1GB就可以使用这种方法。具体思路是：假设整数占用4B(如果占用8B，那么求解思路类似，只不过需要占用更大的内存)，4B也就是32位，可以表示的整数的个数为2的32次幂。因为这道题是查找不重复的数，而不关心具体数字出现的次数，因此可以分别使用2bit来表示各个数字的状态：用00表示这个数字没有出现过，01表示出现过1次，10表示出现了多次，11暂不使用。

　　根据上面的逻辑，在遍历2.5亿个整数的时候，如果这个整数对应的为图中的位为00，那么修改成01，如果为01那么修改为10，如果为10那么保持原值不变。这样当所有数据遍历完成后，可以再遍历一遍位图，位图中为01的对应的数字就是没有重复的数字。

上一篇：哪些数据库可以叫做非关系型数据库？ 下一篇：分库分表能解决MySQL哪些问题？优缺点是什么?