算法-有10亿个整数，要求选取重复次数最多的100个整数

Question

有10亿个整数，要求选取重复次数最多的100个整数，大家说个效率比较高的算法去实现。

Answer 1

加上条件遍历一下就OK了，其他的不用管 去除值来就好

Answer 2

先把数据排序，然后记录每个数连续出现的次数，连续出现次数处于前100的就是要找的前100个数。

Answer 3

用哈希表计数，然后以每个数字的计数值为关键值堆排序，找出前100个。

Answer 4

直接遍历...
记录所有数字出现的次数
大概是遍历一遍的时间

Answer 5

策略

这个问题跟之前回答的一个问题很相似，我就复制一部分过来了。
我们可以使用哈希+桶排序的思路来计算。

解答问题

假设我们可以用的内存是64M，总的数据量是1024 * 64M即64G。

1、首先预设1024个文件作为“桶”，依次读取原始数据的记录，每读到一条记录就进行哈希计算，获得的哈希值余上1024，把这条记录放到那个桶里，即：

bucket_num = hash(record) % 1024

2、由于相同的记录哈希值一定相同，所以重复数据一定落入同一个桶内，对于落入同一个桶内的数据，直接为该数据的数量加一，即桶内的条目都是唯一的，各自记录自己的总重复数量。

3、当一个桶的体积达到64M的时候（应该非常罕见），为该桶增加一个子桶，新的数据进来的时候先在父桶内找相同记录，没有的话在放入子桶，重复数设置为1。

4、当全部数据读取完之后，依次对1024个桶（及其子桶）进行内部排序，可以一次性把64M的数据读入内存快速排序即可，然后再归并父桶及其子桶，最终得到1024个已经内部排序的桶。

5、最后，构造一个容量为100的大堆，遍历1024个桶，每次从桶内取出一个数放进堆中，如果堆中没有数字被替换出来，则换到下一个桶继续取数字放进堆中，如果堆中的数字被换出来一个，则继续从该桶取数据。直到连续1024次替换没有新的数子桶堆中被换出来位置。

6、最后得到的100容量的大堆即为所求。

效率

此方法的优点在于，可以按照具体的机器性能来调整桶的大小，比如你内存够大，可以把桶调整成装下5亿整数的大小，两个桶就够了。

复杂度为：第一次hash遍历：O(n) + 桶内排序：O(m * n * log(n))（m为桶数）+ 100容量的大堆时间 O(m * logm)

Answer 6

采用Hash+小顶堆
Hash就是为了统计每个数出现的次数，然后发生冲突的地方用个链表把它链接起来，在每个节点中存储一个含有data和count成员的结构体，data记录相应的数字，而count记录对应的数字出现的次数，这一步的时间复杂度是o(n).（注意这里虽然数字很多，但是因为会存在大量的重复数据，不用担心最后的空间会有10亿）
然后创建一个大小为100的小顶堆，然后将Hash表中前面100个非空的成员放入小顶堆中，然后将hash表中的其他数据和堆顶出现的次数比较，如果比堆顶出现的次数少，则丢弃当前数，如果大于堆顶元素的出现次数，则替换堆顶，然后进行堆调整，这一步时间复杂度是o(nlog100).

总的时间复杂度是o(n)+o(nlog100)

Answer 7

可以先遍历一遍，使用计数排序策略记录每一个出现的数字的次数。然后通过构造一个100元素的小顶堆来取得出现次数最多的100个元素。

Answer 8

哈细表太浪费内存了，直接用位图。

Answer 9

用一个bit数组 data[十亿]初始化为0 读取数据i，若 data[i] == 0 ，data[i]=1;
否则 记录用一个结构体记录i，并记录他的的次数。最后则可以 求出 出现次数最多的数整数