经典的 Top K 问题,你真的懂了么?

栏目: 后端 · 发布时间: 5年前

内容简介:既然是要前 K 大的数,那么最直接的当然就是排序了,通过如快排等效率较高的排序算法,可以在平均 O(nlogn)的时间复杂度找到结果。这种方式在数据量不大的时候简单可行,但固然不是最优的方法。刚刚提到了快排,熟悉算法题的小伙伴应该知道,快排的 partition 划分思想可以用于计算某个位置的数值等问题,例如用来计算中位数;显然,也适用于计算 TopK 问题

既然是要前 K 大的数,那么最直接的当然就是 排序 了,通过如快排等效率较高的排序算法,可以在平均 O(nlogn)的时间复杂度找到结果。

这种方式在数据量不大的时候简单可行,但固然不是最优的方法。

二. O(n) 时间复杂度的方法

刚刚提到了快排,熟悉算法题的小伙伴应该知道,快排的 partition 划分思想可以用于计算某个位置的数值等问题,例如用来计算中位数;显然,也适用于计算 TopK 问题

经典的 Top K 问题,你真的懂了么?

每次经过划分,如果中间值等于 K ,那么其左边的数就是 Top K 的数据; 当然,如果不等于,只要递归处理左边或者右边的数即可

该方法的时间复杂度是 O(n) ,简单分析就是第一次划分时遍历数组需要花费 n,而往后每一次都折半(当然不是准确地折半),粗略地计算就是 n + n/2 + n/4 +... < 2n,因此显然时间复杂度是 O(n)

对比第一个方法显然快了不少,随着数据量的增大,两个方法的时间差距会越来越大

缺点

虽然时间复杂度是 O(n) ,但是缺点也很明显,最主要的就是内存问题,在海量数据的情况下,我们很有可能没办法一次性将数据全部加载入内存,这个时候这个方法就无法完成使命了

还有一点就是这种思路需要我们修改输入的数组,这也是值得考虑的一点

三. 利用分布式思想处理海量数据

面对海量数据,我们就可以放分布式的方向去思考了

我们可以将数据分散在多台机器中,然后每台机器并行计算各自的 TopK 数据,最后汇总,再计算得到最终的 TopK 数据

这种数据分片的分布式思想在面试中非常值得一提,在实际项目中也十分常见

四. 利用最经典的方法,一台机器也能处理海量数据

其实提到 Top K 问题,最经典的解法还是利用堆。

维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。

当然,如果是求前 K 个最小的数,只需要改为大顶堆即可

经典的 Top K 问题,你真的懂了么?
经典的 Top K 问题,你真的懂了么?
经典的 Top K 问题,你真的懂了么?

对于海量数据,我们不需要一次性将全部数据取出来,可以一次只取一部分,因为我们只需要将数据一个个拿来与堆顶比较。

另外还有一个优势就是对于动态数组,我们可以一直都维护一个 K 大小的小顶堆,当有数据被添加到集合中时,我们就直接拿它与堆顶的元素对比。这样,无论任何时候需要查询当前的前 K 大数据,我们都可以里立刻返回给他。

整个操作中,遍历数组需要 O(n) 的时间复杂度,一次堆化操作需要 O(logK),加起来就是 O(nlogK) 的复杂度,换个角度来看,如果 K 远小于 n 的话, O(nlogK) 其实就接近于 O(n) 了,甚至会更快,因此也是十分高效的。

最后,对于 Java,我们可以直接使用优先队列 PriorityQueue 来实现一个小顶堆,这里给个代码:

public List<Integer> solutionByHeap(int[] input, int k) {
    List<Integer> list = new ArrayList<>();
    if (k > input.length || k == 0) {
        return list;
    }
    Queue<Integer> queue = new PriorityQueue<>();
    for (int num : input) {
        if (queue.size() < k) {
            queue.add(num);
        } else if (queue.peek() < num){
            queue.poll();
            queue.add(num);
        }
    }
    while (k-- > 0) {
        list.add(queue.poll());
    }
    return list;
}
复制代码

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ACM/ICPC程序设计与分析

ACM/ICPC程序设计与分析

沈云付 / 清华大学 / 2010-7 / 39.50元

《ACM/ICPC程序设计与分析(C++实现)》介绍ACM国际大学生程序设计竞赛概况及程序设计基础,系统介绍数论、组合数学、动态规划、计算几何、搜索、图论和网络流等专题的典型算法,挑选历年竞赛中许多有代表性的竞赛题作为例题进行分析,便于学生编程时模仿学习。每章的例题和习题都配有输入输出样例,方便学生在编程时测试与调试程序。《ACM/ICPC程序设计与分析(C++实现)》以C++为程序设计语言,以提......一起来看看 《ACM/ICPC程序设计与分析》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具