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

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

夜无邪 发布于 2016-11-20 字数 86 浏览 1497 回复 9

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

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(9

偏爱自由 2017-11-10 9 楼

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

虐人心 2017-10-20 8 楼

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

想挽留 2017-10-06 7 楼

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

清晨说ぺ晚安 2017-08-30 6 楼

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

灵芸 2017-07-04 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)

灵芸 2017-04-30 4 楼

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

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

泛泛之交 2017-04-01 3 楼

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

泛泛之交 2016-12-20 2 楼

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

归属感 2016-12-11 1 楼

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