当前位置:网站首页>【快排】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
边栏推荐
- Introduction to servlet listener & filter
- 基于uniapp异步封装接口请求简介
- Summary of JVM knowledge points - continuously updated
- Temperature and humidity monitoring + timing alarm system based on 51 single chip microcomputer (C51 source code)
- Kernel error: no rule to make target 'Debian / canonical certs pem‘, needed by ‘certs/x509_ certificate_ list‘
- Go language mapping operation
- MySQL basic statement query
- Introduction to metalama 4 Use fabric to manipulate items or namespaces
- After the data of El table is updated, the data in the page is not updated this$ Forceupdate() has no effect
- Servlet监听器&过滤器介绍
猜你喜欢
Huawei cloud MVP email
世界读书日:我想推荐这几本书
STM32 is connected to the motor drive, the DuPont line supplies power, and then the back burning problem
The accuracy and speed are perfectly balanced, and the latest image segmentation SOTA model is released!!!
Design and manufacture of 51 single chip microcomputer solar charging treasure with low voltage alarm (complete code data)
Record Alibaba cloud server mining program processing
Important knowledge of network layer (interview, reexamination, term end)
About the 'enum' enumeration type and structure.
Record the problems encountered in using v-print
How to click an object to play an animation
随机推荐
Record the problems encountered in using v-print
世界读书日:我想推荐这几本书
mui 微信支付 排坑
CMSIS cm3 source code annotation
PC starts multiple wechat at one time
AUTOSAR from introduction to mastery 100 lectures (51) - AUTOSAR network management
How to convert opencv pictures to bytes
Recovering data with MySQL binlog
8086 of x86 architecture
nodeJs + websocket 循环小案例
MySQL —— 16、索引的数据结构
Go language slicing operation
Connect orcale
Office 2021 installation package download and activation tutorial
5 free audio material websites, recommended collection
31. Next arrangement
hbuilderx + uniapp 打包ipa提交App store踩坑记
Introducing vant components on demand
filter()遍历Array异常友好
1130 - host XXX is not allowed to connect to this MySQL server error in Navicat remote connection database