40亿个QQ号码如何去重？

问题引入

文件中有40亿个QQ号码，请设计算法对QQ号码去重，相同的QQ号码仅保留一个，内存限制1G.

问题的变型：42亿QQ，O(1)时间复杂度完成查找

问题思路

排序

经过排序后，相同的QQ号前后相邻，然后遍历一遍就可去重了。
但排序的最好效率 nlgn，在面对如此大的数据规模，运行时间也会很长，且有内存限制

Set

涉及到去重问题，我们第一时间想到的可能就是set了，以Java的HashSet为例，其底层实现为 数组 + 链表 + 红黑树，其还是涉及到存储问题，40亿的QQ号（最大为13位）已经超过了int 范围，直接存储的话，空间要求还是无法满足

位图 bitmap

其一个位置代表一个数，即一个下标也就是一个数，，这样一位就可以代表一个数，存储空间也可以满足要求
40亿 = 4,000,000,000 bit
   1G = 8,589,934,592 bit

值 0/1 代表了这个数存不存在，也就自动实现了去重。

参考

[1] 腾讯三面：40 亿个 QQ 号码如何去重？ https://zhuanlan.zhihu.com/p/442732557