腾讯三面：40亿个QQ号码如何去重？
dotNET全栈开发
共 4477字，需浏览 9分钟
·
2021-12-01 17:08
在腾讯面试的三面环节，非常有意思。具体的题目如下：
文件中有40亿个QQ号码，请设计算法对QQ号码去重，相同的QQ号码仅保留一个，内存限制1G.
这个题目的意思应该很清楚了，比较直白。为了便于大家理解，我来画个动图玩玩，希望大家喜欢。
在原题中，实际有40亿个QQ号码，为了方便起见，在图解和叙述时，仅以4个QQ为例来说明。
方法一：排序
很自然地，最简单的方式是对所有的QQ号码进行排序，重复的QQ号码必然相邻，保留第一个，去掉后面重复的就行。
原始的QQ号为：
排序后的QQ号为：
去重就简单了：
可是，面试官要问你，去重一定要排序吗？显然，排序的时间复杂度太高了，无法通过腾讯面试。
方法二：hashmap
既然直接排序的时间复杂度太高，那就用hashmap吧，具体思路是把QQ号码记录到hashmap中：
mapFlag[123] = true
mapFlag[567] = true
mapFlag[123] = true
mapFlag[890] = true由于hashmap的去重性质，可知实际自动变成了：
mapFlag[123] = true
mapFlag[567] = true
mapFlag[890] = true很显然，只有123，567，890存在，所以这也就是去重后的结果。
可是，面试官又要问你了：实际要存40亿QQ号码，1G的内存够分配这么多空间吗？显然不行，无法通过腾讯面试。
方法三：bitmap
来看绝招！我们可以对hashmap进行优化，采用bitmap这种数据结构，可以顺利地同时解决时间问题和空间问题。
在很多实际项目中，bitmap经常用到。我看了不少组件的源码，发现很多地方都有bitmap实现，bitmap图解如下：
这是一个unsigned char类型，可以看到，共有8位，取值范围是[0, 255]，如上这个unsigned char的值是255，它能标识0~7这些数字都存在。
评论