寻找最大的K个数

解法1:可以使用容量为K的最小堆来存储最大的K个数,最小堆的堆顶元素就是最大K个数中最小的一个。每次新考虑一个数X,如果X比堆顶的元素Y小,则不需要改变原来的堆。如果X比Y大,那么就用X替换堆顶的元素Y,并调整新的堆成为最小堆。调整堆的时间复杂度为O(log2K)。
这样的话,算法扫描所有的数据一次,总的时间复杂度为O(N*log2K)。

解法2:如果所有N个数都是正整数,并且它们的取值范围不太大,都在(0,MAXN)区间的话,可以考虑申请一个空间,例如数组count[MAXN],记录下每个整数出现的个数(count[i]表示整数i在所有整数中出现的个数)。我们只须扫描一遍就可以得到count数据,然后,从数组最后往前数出K个数就OK了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 解法1、 常规方法 ,如果数组很大呢?是放在堆还是放在栈呢?? 这个是一个问题;时间复杂度是O(N *logN) ...
    helinyu阅读 1,247评论 0 1
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,354评论 0 33
  • 解法一 最容易想到的方法是先对元素进行排序,然后取出前k个数,总时间复杂度O(n*logN)。你一定注意到了,当k...
    书呆子的复仇阅读 9,332评论 2 1
  • 寻找最小的 k 个数 题目描述: 输入 n 个整数,输出其中最小的 k 个。 分析和解法: 解法一:排序输出 要求...
    MinoyJet阅读 3,715评论 0 0
  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    叶总韩阅读 10,542评论 0 41

友情链接更多精彩内容