海量数据Top K问题的解决方案

2019年10月16日21:30:33 评论 74

Top K是很常见的一种问题,是指在N个数的无序序列中找出最大的K个数,而其中的N往往都特别大,对于这种问题,最容易想到的办法当然就是先对其进行排序,然后直接取出最大的K个元素就行了,但是这种方法往往是不可靠的,不仅时间效率低而且空间开销大,排序是对所有数都要进行排序,而实际上,这类问题只关心最大的K个数,并不关心序列是否有序,因此,排序实际上是浪费了的很多资源都是没必要的。

海量数据Top K问题的解决方案

题目:

输入 n 个整数,找出其中最大的 k 个数。例如输入4、5、1、6、2、7、3、8 这8个数字,则最大的4个数字是5、6、7、8。

解法一:基于快排的O(n)的算法
如果基于数组的第 k 个数字来调整,使得比第 k 个数字小的所有数字都位于数组的左边,比第 k 个数字大的所有数字都位于数组的右边。这样调整之后,位于数组中左边的 k 个数字就是最小的 k 个数字(这 k 个数字不一定是排序的)。

采用上面的思路是有限制的,比如需要修改输入的数组,因为函数 Partition 会调整数组中的顺序,当然了,这个问题完全可以通过事先拷贝一份新数组来解决。值得说明的是,这种思路是不适合处理海量数据的。若是遇到海量数据求最小的 k 个数的问题,可以使用下面的解法。

解法二:最小堆法

利用最小堆的思想,先读取前k个元素,建立一个最小堆。然后将剩余的所有元素依次与堆顶元素进行比较,如果大于堆顶元素,则堆顶弹出,否则,压入下一个数组元素继续比较,只要维护大小为k的堆就可以了,此方法适合处理海量数据,时间复杂度为O(nlogk)。java的PriorityQueue可以实现最小堆。

也可以将上述代码改为手动实现最小堆的方式,代码如下:

若是遇到此类求海量数据中最小的 k 个数的问题,只需改用最大堆即可。构建最大堆,需要重写compare方法。

 

最后更新:2019-10-20
weinxin
关于本站
本站是一个分享建站经验、SEO优化、互联网技术以及日常生活的个人生活博客。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: