内容简介:既然是要前 K 大的数,那么最直接的当然就是排序了,通过如快排等效率较高的排序算法,可以在平均 O(nlogn)的时间复杂度找到结果。这种方式在数据量不大的时候简单可行,但固然不是最优的方法。刚刚提到了快排,熟悉算法题的小伙伴应该知道,快排的 partition 划分思想可以用于计算某个位置的数值等问题,例如用来计算中位数;显然,也适用于计算 TopK 问题
既然是要前 K 大的数,那么最直接的当然就是 排序 了,通过如快排等效率较高的排序算法,可以在平均 O(nlogn)的时间复杂度找到结果。
这种方式在数据量不大的时候简单可行,但固然不是最优的方法。
二. O(n) 时间复杂度的方法
刚刚提到了快排,熟悉算法题的小伙伴应该知道,快排的 partition 划分思想可以用于计算某个位置的数值等问题,例如用来计算中位数;显然,也适用于计算 TopK 问题
每次经过划分,如果中间值等于 K ,那么其左边的数就是 Top K 的数据; 当然,如果不等于,只要递归处理左边或者右边的数即可
该方法的时间复杂度是 O(n) ,简单分析就是第一次划分时遍历数组需要花费 n,而往后每一次都折半(当然不是准确地折半),粗略地计算就是 n + n/2 + n/4 +... < 2n,因此显然时间复杂度是 O(n)
对比第一个方法显然快了不少,随着数据量的增大,两个方法的时间差距会越来越大
缺点
虽然时间复杂度是 O(n) ,但是缺点也很明显,最主要的就是内存问题,在海量数据的情况下,我们很有可能没办法一次性将数据全部加载入内存,这个时候这个方法就无法完成使命了
还有一点就是这种思路需要我们修改输入的数组,这也是值得考虑的一点
三. 利用分布式思想处理海量数据
面对海量数据,我们就可以放分布式的方向去思考了
我们可以将数据分散在多台机器中,然后每台机器并行计算各自的 TopK 数据,最后汇总,再计算得到最终的 TopK 数据
这种数据分片的分布式思想在面试中非常值得一提,在实际项目中也十分常见
四. 利用最经典的方法,一台机器也能处理海量数据
其实提到 Top K 问题,最经典的解法还是利用堆。
维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。
当然,如果是求前 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; } 复制代码
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 经典动态规划问题:高楼扔鸡蛋
- google经典算法面试题-鸡蛋问题
- [经典算法]8皇后问题sql求解(回溯算法)
- 15个经典的Spring面试常见问题
- 服务端经典的C10k问题(译)
- 从经典论文看YouTube深度学习推荐系统的十大工程问题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
ACM/ICPC程序设计与分析
沈云付 / 清华大学 / 2010-7 / 39.50元
《ACM/ICPC程序设计与分析(C++实现)》介绍ACM国际大学生程序设计竞赛概况及程序设计基础,系统介绍数论、组合数学、动态规划、计算几何、搜索、图论和网络流等专题的典型算法,挑选历年竞赛中许多有代表性的竞赛题作为例题进行分析,便于学生编程时模仿学习。每章的例题和习题都配有输入输出样例,方便学生在编程时测试与调试程序。《ACM/ICPC程序设计与分析(C++实现)》以C++为程序设计语言,以提......一起来看看 《ACM/ICPC程序设计与分析》 这本书的介绍吧!