LeetCode 215. 数组中的第K个最大元素
发布日期:2021-06-20 05:37:26
浏览次数:9
分类:技术文章
本文共 1077 字,大约阅读时间需要 3 分钟。
题目
在未排序的数组中找到第 k
个最大的元素。请注意,它是数组有序排列后的第 k
个最大元素,而不是第 k
个不同元素。
[3,2,1,5,6,4]
和k = 2
,返回 5
。 注意事项: 你可以假设 k
总是有效的,1 ≤ k ≤
数组的长度。 方法一:
先对数组快速排序再选择第K大的。时间复杂度O(nlgn) 空间复杂度O(1)
方法二:
维持一个大小为K的最小堆,遍历整个数组和堆顶比较。时间复杂度O(n lgK)空间复杂度 O(k)
public int findKthLargest(int[] nums, int k) { //找到第k大的数 PriorityQueueheap =new PriorityQueue<>(); for (int i = 0; i < k; i++) { heap.add(nums[i]); } for (int i = k; i < nums.length; i++) { if (heap.peek()
方法三:
类似快排的思想:选择一个数,将比它小的移动到左边,比它大的移动到右边。如果位置是n-k,输出;否则左边或右边继续查找。时间复杂度O(n lgn) 空间复杂度O(1)
方法四:
如果变态要求原数组不能修改(不能移动),并且额外空间复杂度为O(1)
那么上述方法就全都不能用了。考虑用二进制解法。比如对于int型正整数,4字节,即32位,如果第i位 置1,保持前i-1位不变,那么根据前i位可以将数组分成两部分,即可以起到二分的作用。具体举例如下,数组为[2,6,4,1,3,5],然后找第2大的数,即k=2。int型对应32位bit标号为31,30,29...3,2,1,0:
十进制 | 二进制 |
---|---|
2 | 10 |
6 | 110 |
4 | 100 |
1 | 1 |
3 | 11 |
5 | 101 |
1、bit位第2位为1,可以将数组分为[2,1,3]和[6,4,5]两部分。由于需要找第2大,所以在数组[6,4,5]中继续查找。
2、继续考察bit位第1位为1,则数组[6,4,5]可以分为[4,5]和[6]两部分,此时较大的数组为[6]只有一个元素,所以在较小的数组[4,5]中继续找第1大的数(这里要注意一下,由于[6]只有一个,所以k=k-1=1) 3、继续考察第0位为1,则数组[4,5]可以分为[4]和[5]两组,较大数组[5]只有1个,而此时k=1,故可以直接取出5即为所求。
参考:
转载地址:https://blog.csdn.net/h2453532874/article/details/90035312 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年03月10日 15时52分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
centos 7 mysql图形界面_centos7-vnstat图形界面搭建
2019-04-21
java 防渗透_「java、工程师工作经验怎么写」-看准网
2019-04-21
java中跳出当前循环怎么做_在java中,如何跳出当前的多重循环?
2019-04-21
java16下载_java lombok下载
2019-04-21
python 图像处理与识别书籍_Python图像处理之识别图像中的文字(实例讲解)
2019-04-21
java安全初始化_java安全编码指南之:声明和初始化
2019-04-21
java jstat gc_分析JVM GC及内存情况的方法
2019-04-21
php linux权限,Linux权限详细介绍
2019-04-21
典型环节的matlab仿真分析,典型环节的MATLAB仿真.doc
2021-06-24
Php contenttype类型,各种类型文件的Content Type
2021-06-24
php使用redis持久化,redis如何持久化
2021-06-24
php7.1解压包安装,【Swoole】php7.1安装swoole扩展
2021-06-24
linux centos删除安装的包,CentOS yum认为已删除的软件包仍在安装中
2021-06-24
酒店管理系统c语言带注释,酒店管理系统--C语言版.pdf
2019-04-21
c语言 实现sizeof功能,C语言简单实现sizeof功能代码
2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值
2019-04-21