2.5亿个整数的去重

发布时间:2020-06-10 11:00:00
阅读量:51
作者:猎维人工智能培训
海量数据处理面试题

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

分析

采用2位图(每个数分配2位,00表示不存在,01表示出现一次,10表示出现多次,11无意义),共需内存232 × 2=1 GB内存,可以接受。

然后扫描这2.5亿个整数,查看位图中相对应的位,如果是00就变为01,如果是01就变为10,如果是10就保持不变。扫描完之后,查看位图,把对应位是01的整数输出即可。也可以先划分成小文件,然后在小文件中找出不重复的整数,并排序,最后归并,归并的同时去除重复的数。

扩展

所谓位图,就是用一个位(bit)来标记某个元素对应的值,而键就是该元素。由于采用了位为单位来存储数据,因此可以大大节省存储空间。

位图通过使用位数组来表示某些元素是否存在,可进行数据的快速查找、判重、删除。

来看一个具体的例子。假设我们要对0~7中的5个元素(4, 7, 2, 5, 3)进行排序(假设这些元素没有重复),此时就可以采用位图的方法来达到排序的目的。因为要表示8个数,所以只需要8位,由于8位等于1字节,所以开辟1字节的空间,并将这个空间的所有位都置为0,如图1所示。

图1

然后遍历这5个元素。因为待排序序列的第一个元素是4,所以把4对应的位重置为1(可以这样操作:p + (i/8) | (001 << (i % 8)) 。当然,这里的操作涉及big-endian和little-endian[ little-endian就是低位字节排放在内存的低地址端,高位字节排放在内存的高地址端。big-endian就是高位字节排放在内存的低地址端,低位字节排放在内存的高地址端。]的情况,这里默认为big-endian),又由于是从0开始计数的,所以把第5位重置为1,如图所示。

然后再处理待排序序列的第二个元素7,将第8个位重置为1。接着再处理待排序序列的第三个元素2,一直到处理完所有的元素。将相应的位置为1后,这时候内存的位的状态如图2所示。

图2

现在遍历一遍这个位区域,将某位是1的位的编号(2, 3, 4, 5, 7)输出,这样就达到了排序的目的。


本题解析节选自July一书《编程之法:面试和算法心得》第六章 海量数据处理。

更多资讯