当前位置:网站首页>【快排】215. 数组中的第K个最大元素
【快排】215. 数组中的第K个最大元素
2022-04-23 13:07:00 【不爱研究的研究僧】
题目:
给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
题解:
快排每轮partition就可以将选中的pivot放到其最终有序位置,当某轮pivot被放到第k大元素位置(从小到大有序序列的下标n-k处)时,确定该pivot为结果
pivot的选择利用随机数可以防止最差时间复杂度。
nextInt()用法:
会随机生成一个整数,这个整数的范围就是int类型的范围-2^31 ~ 2^31-1,但是如果在nextInt()括号中加入一个整数a那么,这个随机生成的随机数范围就变成[0,a)。
class Solution {
public int findKthLargest(int[] nums, int k) {
//第k大元素,即排序后下标为n-k的元素,使用partition方法确定下标n-k元素
int target = nums.length - k;
int from = 0, to = nums.length - 1;
while (true) {
int idx = partition(nums, from, to); //每次partition返回pivot插入的位置
if (idx == target) { //如果插入的位置是目标位置,找到第k大元素
return nums[target];
} else if (idx > target) { //如果插入的位置大于目标位置,目标位置搜索范围应该在idx左边
to = idx - 1;
} else { //如果插入的位置小于目标位置,目标位置搜索范围应该在idx右边
from = idx + 1;
}
}
}
Random rand = new Random();
//返回单次partition确定pivot元素固定到的位置
private int partition(int[] nums, int from, int to) {
int pivotIndex = rand.nextInt(to - from + 1) + from;
int pivot = nums[from];
//随机pivot交换到头部
int temp = nums[from];
nums[from] = pivot;
nums[pivotIndex] = temp;
int left = from, right = to;
while (left < right) {
while (left < right && nums[right] >= pivot) { //从右往左找到第一个<pivot的
right--;
}
if (left < right) {
nums[left] = nums[right];
}
while (left < right && nums[left] <= pivot) { //从左往右找到第一个>pivot的
left++;
}
if (left < right) {
nums[right] = nums[left];
}
}
nums[left] = pivot; //最后把pivot放到left的位置
return left;
}
}
参考:力扣
版权声明
本文为[不爱研究的研究僧]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_43955488/article/details/124360180
边栏推荐
- 这几种 VSCode 扩展是我最喜欢的
- 拥抱机器视觉新蓝海,冀为好望开启数字经济发展新“冀”遇
- Teach you to quickly develop a werewolf killing wechat applet (with source code)
- HQL statement tuning
- STM32 is connected to the motor drive, the DuPont line supplies power, and then the back burning problem
- (1) Openjuterpyrab comparison scheme
- three. JS text ambiguity problem
- mysql支持ip访问
- AUTOSAR from introduction to mastery 100 lectures (50) - AUTOSAR memory management series - ECU abstraction layer and MCAL layer
- After the data of El table is updated, the data in the page is not updated this$ Forceupdate() has no effect
猜你喜欢
Jupiter notebook installation
Record Alibaba cloud server mining program processing
mui + hbuilder + h5api模拟弹出支付样式
Customize the shortcut options in El date picker, and dynamically set the disabled date
HQL find the maximum value in a range
Customize classloader and implement hot deployment - use loadclass
8086 of x86 architecture
The quill editor image zooms, multiple rich text boxes are used on one page, and the quill editor upload image address is the server address
About the 'enum' enumeration type and structure.
内核错误: No rule to make target ‘debian/canonical-certs.pem‘, needed by ‘certs/x509_certificate_list‘
随机推荐
CMSIS cm3 source code annotation
PC starts multiple wechat at one time
Record Alibaba cloud server mining program processing
Free and open source intelligent charging pile SaaS cloud platform of Internet of things
7_Addmodule和基因加和法add 得到的细胞类型打分在空间上空转对比
AUTOSAR from introduction to mastery 100 lectures (51) - AUTOSAR network management
4.22 study record (you only did water problems in one day, didn't you)
将opencv 图片转换为字节的方式
Three channel ultrasonic ranging system based on 51 single chip microcomputer (timer ranging)
(1) Openjuterpyrab comparison scheme
Navicat远程连接数据库 出现 1130- Host xxx is not allowed to connect to this MySQL server错误
1130 - host XXX is not allowed to connect to this MySQL server error in Navicat remote connection database
Start mqbroker CMD failure resolution
CVPR 2022 & ntire 2022 | the first transformer for hyperspectral image reconstruction
100 GIS practical application cases (52) - how to keep the number of rows and columns consistent and aligned when cutting grids with grids in ArcGIS?
Melt reshape decast long data short data length conversion data cleaning row column conversion
Introducing vant components on demand
7_ The cell type scores obtained by addmodule and gene addition method are compared in space
Complete project data of UAV apriltag dynamic tracking landing based on openmv (LabVIEW + openmv + apriltag + punctual atom four axes)
31. 下一个排列