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大的数        PriorityQueue
heap =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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:LeetCode - Java 206 反转链表
下一篇:LeetCode 674. 最长连续递增序列 java

发表评论

最新留言

表示我来过!
[***.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
java程序中执行maven_java – 将一个enviornment变量传递给Maven中的已执行进程 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 pclzip.lib.php,php使用pclzip类实现文件压缩的方法(附pclzip类下载地址) 2019-04-21
php dns更新,php_mzdns: 站群,大量域名 通过 dns 服务商 api 批量添加 ip 工具。你懂的~ 基于 mzphp2 框架。... 2019-04-21
jdk 1.8 java.policy,JDK1.8 导致系统报错:java.security.InvalidKeyException:illegal Key Size 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