文章目录加载中

topK 问题:如何在N个数中找到前K个最大的数

# 方案 1: 排序 + 遍历

先对 N 个数做一次整体从大到小的快速排序,然后返回排序结果集合的前 K 个数。

优点:思路简单,时间复杂度是 O(NlogN)

缺点:当数据量(N)过大的时候,例如 10 亿个数字,一次读入内存不现实,需要考虑其它方案。

# 方案 2: 排序 + 文件切分

借助分布式的思想,分而治之计算部分结果,最终再汇总所有结果。

将 N 个数,切分成 m 个文件,分别存储在磁盘上。读取每个文件数据,进行快速排序,将结果存储到文件中。

然后读取从排序后的文件中,每个文件都读取前 k 个数据(只需要最大的 k 个数),然后将它们合并成有序的数组(处理思路与将多个有序链表合并成一个有序链表相似),再返回前 k 个数即可。

优点:时间复杂度是 O(NlogN),借助分布式思想,能够处理大规模数据

缺点:需要磁盘 IO,这个无法规避。但 IO 次数等于 m,文件不会切的太碎,所以 IO 成本可控。

注意:最后一步也可以从 m 个文件上依次读取数据(一个个读取),按照将多个有序列表合并成一个有序列表的思路,将他们合并成一个有序列表,返回前 k 个数。但这种方法,IO 次数为 N;而一次读取前 k 个数,IO 次数仅为 m。

# 方案 3: 堆 + 批量处理

由于要求 k 个最大值,所以首先从原始文件中,一次读取 k 个数,并且建立大小为 k 的小顶堆。

然后继续从原始文件中,读取数据。这里也不是一个个读取(IO 次数过多),而是批量读取多个数据(满足机器内存要求即可)。假设一次批量读取(N/4)个数据。

那么对这(N/4)个数据,开始遍历。如果当前元素比堆顶元素大,那么堆推出顶部元素,推入当前元素。堆的大小始终保持为 k。

然后按照每次 25%的规模,继续读取剩下 75%的数据,重复上述操作。

优点:时间复杂度是 O(N);并且 IO 次数取决于批量读取次数,IO 成本可控;实现也不复杂。

# 总结

对比以上 3 种方案,最小堆+批量处理方法最好。

题外话,对于方案 1,如果数据不多,可以一次全部读入内存,那么可以在快排的 partition 过程中,找到前 k 个最大的元素,时间复杂度是 O(N)。leetcode 上有类似的题,不再冗赘。这种思路代码不好写,不如直接上堆好理解,时间复杂度也一样。

本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog