面试刷题网站：天津炒股配资开户
今天，我们来聊一道常见的考题，也出现在腾讯面试的三面环节，非常有意思。具体的题目如下：
文件中有40亿个QQ号码，请设计算法对QQ号码去重，相同的QQ号码仅保留一个，内存限制1G.
这个题目的意思应该很清楚了，比较直白。为了便于大家理解，我来画个动图玩玩，希望大家喜欢。
能否做对这道题目，很大程度上就决定了能否拿下腾讯的offer，有一定的技巧性，一起来看下吧。
在原题中，实际有40亿个QQ号码，为了方便起见，在图解和叙述时，仅以4个QQ为例来说明。
方法一：排序
展开剩余84%很自然地，最简单的方式是对所有的QQ号码进行排序，重复的QQ号码必然相邻，保留第一个，去掉后面重复的就行。
原始的QQ号为：
排序后的QQ号为：
去重就简单了：
可是，面试官要问你，有比排序更快的方式吗？显然，简单的排序，无法通过腾讯面试。
方法二：hashmap
既然直接排序的时间复杂度太高，那就用hashmap吧，具体思路是把QQ号码记录到hashmap中：
由于hashmap的去重性质，可知实际自动变成了：
很显然，只有123，567，890存在，所以这也就是去重后的结果。
可是，面试官又要问你了：实际要存40亿QQ号码，1G的内存够分配这么多空间吗？显然不行，无法通过腾讯面试。
方法三：外部排序
这时候我们会深刻意识到，这是海量数据问题。看过很多面经的求职者，自然想到文件切割的方式，避免内存过大。
为了走捷径，我们可以直接使用 `sort -un qq.txt`命令进行外部排序然后去重，其中 -n 表示按数值排序，-u 去重。
外部排序采用 “分治 + 多路归并” 的方式，先排序再去重（排序后重复数据会相邻，便于删除），可以对远大于内存空间的大文件进行去重。
外部具体步骤如下：
1.分块：假设内存仅能容纳 100MB 数据，将 40 亿 QQ 号的大文件，按每个 QQ 号 8 字节算约32GB，按 100MB 为单位拆分成 320 个小文件；逐个读取小文件到内存，用快速排序 / 归并排序等算法对其内部的 QQ 号排序，得到有序小文件。
2.多路归并：同时读取所有 320 个有序小文件的 “首元素”，放入内存中的堆里；
每次从堆中取出 “最小的 QQ 号” 写入最终大文件，然后从该 QQ 号所属的有序小文件中读取下一个元素补充到堆中；
重复此过程，直到所有有序小文件的元素都被取出，最终得到一个 全局有序 的 QQ 号大文件。
3.去重：遍历全局有序文件，记录 “上一个读取的 QQ 号”；若当前读取的 QQ 号与 “上一个” 相同，则跳过；若不同，则保留当前 QQ 号并更新 “上一个” 的值；遍历结束后，保留的 QQ 号即为去重结果。
这样貌似就万事大吉了。但是我只能坦白地说，高兴得有点早哦。虽然生产环境这么做一点问题都没有，但是在我们面试过程中，面试官会接着为难你：这么多的文件操作，效率自然不高啊，依旧还是 无法通过腾讯面试。
方法四：bitmap
来看绝招！我们可以对hashmap进行优化，采用bitmap这种数据结构，可以顺利地同时解决时间问题和空间问题。
在很多实际项目中，bitmap经常用到。我看了不少组件的源码，发现很多地方都有bitmap实现，bitmap图解如下：
这是一个unsigned char类型，可以看到，共有8位，取值范围是[0, 255]，如上这个unsigned char的值是255，它能标识0~7这些数字都存在。
同理，如下这个unsigned char类型的值是254，它对应的含义是：1~7这些数字存在，而数字0不存在：
由此可见，一个unsigned char类型的数据，可以标识0~7这8个整数的存在与否。以此类推：
一个unsigned int类型数据可以标识0~31这32个整数的存在与否。
两个unsigned int类型数据可以标识0~63这64个整数的存在与否。
一个unsigned int类型数据可以标识0~31这32个整数的存在与否。
两个unsigned int类型数据可以标识0~63这64个整数的存在与否。
显然，可以推导出来：512MB大小足够标识所有QQ号码的存在与否，请注意：QQ号码的理论最大值为2^32 - 1，大概是43亿左右。
接下来的问题就很简单了：用512MB的unsigned int数组来记录文件中QQ号码的存在与否，形成一个bitmap，比如：
实际上就是：
然后从小到大遍历所有正整数(4字节)，当bitmapFlag值为1时，就表明该数是存在的。
而且，从上面的过程可以看到，自动实现了去重。显然，这种方式可以通过腾讯的面试。
加点难度，内存只有100MB
如果是一个心狠手辣的面试官，他可能会继续追问： 当内存更小，比如仅 100MB时，你又该如何应对？
显然，此时空间无法容纳完整位图，我们得用 “分治思想” 将海量数据拆成内存可容纳的小块，逐块处理。
以 100MB 内存为例, 选择 QQ 号的最高 3 位作为分块依据, 3 位二进制可表示 0~7 共 8 个区间，刚好将 40 亿数据平均分成 8 块，每块数据量约 5 亿，对应位图大小 = 5 亿 bit = 62.5 MB ≤ 100MB。
首先根据 QQ 号的最高 3 位将其分组，分别存放在 8 个文件中。然后读取每个分片文件，使用位图进行去重。最后，将 8 个分片的结果拼接起来即可。
海量数据的问题，要具体问题具体分析，不要眉毛胡子一把抓。有些人完全不刷题天津炒股配资开户，肯定不行。有些人刷题后不加思考，不会变通，也是不行的。好了，先说这么多。牛哥也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。
发布于：广东省中博策略提示：文章来自网络，不代表本站观点。
