page contents

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

轩辕小不懂 发布于 2021-10-08 11:13
阅读 566
收藏 0
分类:Golang

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

2102
Nen
Nen
- 程序员

分析解答:由于这道题目与前面的题目类似,也是无法一次性把所有数据加载到内存中,因此也可以采用类似的方法求解。

方法一:分治法

采用Hash的方法,把这2.5亿个数划分到更小的文件中,从而保证每个文件的大小不超过可用的内存的大小。然后对于每个小文件而言,所有的数据可以一次性被加载到内存中,因此可以使用hash_map或hash_set来找到每个小文件中不重复的数。当处理完所有的文件后就可以找出这2.5亿个整数中所有的不重复的数。

方法二:位图法

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

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

请先 登录 后评论