扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 海量数据高频面试题 > 6.2.5亿个整数中找出不重复的整数,内存空间不足以容纳这2.5亿个整数

方法一:分治法

先将2.5已个整数通过hash取余,存到多个文件中,这时相同的整数会存入同一个文件。第二步是通过HashMap统计每个小文件中整数出现的频率(key为整数,value为频率),将所有value为1的整数存到单独的文件中,即为不重复的整数

方法二:位图法

如果对布隆过滤器有了解的同学一定记得位图是什么,布隆过滤器在面试中也是经常问到的,下面简答说下什么是位图

简单来说,位图就是,用每一位来存放某种状态,通常是用来判断某个数据存不存在的。位图可以用数组实现的,数组的每一个元素的每一个二进制位都可以表示一个数据在或者不在,0表示数据存在,1表示数据不存在。如下,表示0-6中的元素,0-6中只有7个数,所以用7bit足以表示,例如5可以表示为

[0,0,0,0,0,1,0]

那为什么要使用位图,使用位图有什么好处呢?

使用位图可以大大缩短存储空间,一个int占用4byte,1byte=8bit,也就说本来4byte只能存1个整数,而现在4type可以存32个整数。

回到本题,要找出不重复的整数,那么一个整数可以有三种状态,即不存在、存在1次、存在多次,根据题目需要找出的是存在1次的

对于三种状态只用0或1肯定是表示不了的,所以可以用两位来表示整数的状态,00表示不存在,01表示存在1次,10表示存在多次。

具体做法,首先遍历 2.5 亿个整数,查看对应位图中对应的位,如果是 00,则变为 01,如果是 01 则变为 10,如果是 10 则保持不变。最后遍历位图,找出01对应的整数,即为2.5亿整数中只出现一次的整数


点击面试手册,获取本站面试手册PDF完整版