背??景在找工作之前，在腾讯面试的时候遇到了一个很有意思的面试题。当时我想起来我没有当场回答。后来回家想了想。其实并没有那么难，而且还蛮有趣的。分享给大家，希望对你有用。以下文件中有20亿个QQ号。请设计一种算法对QQ号码进行去重。相同QQ号只保留一个，内存限制1G。这道题的意思应该很清楚了，但是为了让大家更容易理解，我画了一个很有年代感的动画。我希望你喜欢它。方法一、排序去除重复。一，只需删除其余的重复项。整个过程如下图动画所示。虽然这样可以解决问题，但是排序往往很复杂，所以一定不是最优解。二、hashmap如果排序的复杂度太高，那就直接用hashmap好了，hashmap的复杂度是O(1)，思路其实很简单，就是直接在hashmap中记录qq号，如果是PHP，可以直接记录在数组中hashMap[123]=truehashMap[456]=truehashMap[123]=truehashMap[789]=true由于hashmap自动去重，自动变成：hashMap[123]=truehashMap[456]=truehashMap[789]=true显然只有123、456、789存在，所以这是去重后的结果。但是，面试官又会问你：1G的内存够分配那么大的空间来实际存储20亿个QQ号吗？显然不是，你这样回答还是过不了腾讯面试。方法3位图看绝招！我们可以对hashmap进行优化，利用bitmap的数据结构来顺利解决时间和空间上的问题。如果你对位图不是很熟悉，可以看我的两篇关于位图（位操作）在redis中的实际应用的文章。12306抢票算法竟然曝光！！！很简单。对位图有了大致的了解后，我们可以直接将已有qq号对应的位置标记为1，只要下次查询时对应的位为1，那么就是重复的qq号，因为位图是一种of非常节省空间的数据结构，因此可以满足1G以内的内存要求。好了，今天就先分享到这里吧，欢迎关注我的公众号——程序员小凡。
