BM47. 寻找第K大
描述
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
示例1
输入:
[1,3,5,2,2],5,3
输出:
2
示例2
输入:
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
输出:
9
说明:
去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9Rust 解法, 执行用时: 20ms, 内存消耗: 3252KB, 提交时间: 2022-06-09
struct Solution{
}
impl Solution {
fn new() -> Self {
Solution{}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
pub fn findKth(&self, a: Vec<i32>, n: i32, K: i32) -> i32 {
// write code here
if K > n {
return -1;
}
let mut nums = a.clone();
let (mut lo, mut hi) = (0 , n as usize - 1);
while lo < hi {
let midIndex = lo + (hi - lo) / 2;
nums.swap(midIndex, hi);
let pivot = nums[hi];
let mut i = lo;
for j in lo..hi {
if nums[j] > pivot {
nums.swap(i,j);
i += 1;
}
}
nums.swap(i, hi);
if i == (K as usize - 1) {
break;
} else if i < (K as usize - 1) {
lo = i + 1;
} else {
hi = i - 1;
}
}
nums[(K - 1) as usize]
}
}
Rust 解法, 执行用时: 22ms, 内存消耗: 3212KB, 提交时间: 2022-04-03
struct Solution{
}
impl Solution {
fn new() -> Self {
Solution{}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
pub fn findKth(&self, a: Vec<i32>, n: i32, k: i32) -> i32 {
// write code here
let mut nums = a;
let last_parent = self.parent(n);
for i in (0..=last_parent).rev() {
self.move_down(&mut nums[..], i);
}
for end in (n-k+1..n).rev() {
nums.swap(0, end as usize);
self.move_down(&mut nums[..end as usize], 0);
}
nums[0]
}
fn move_down(&self, nums: &mut [i32], mut parent: i32) {
let last = nums.len() - 1;
loop {
let left = self.left_child(parent);
let right = self.right_child(parent);
if left as usize > last {
break;
}
let child = if right as usize <= last && nums[left as usize] < nums[right as usize] { right } else { left };
if nums[child as usize] > nums[parent as usize] {
nums.swap(child as usize, parent as usize);
}
parent = child;
}
}
fn parent(&self, child: i32) -> i32 {
(child / 2) - 1
}
fn left_child(&self, parent: i32) -> i32 {
parent * 2 + 1
}
fn right_child(&self, parent: i32) -> i32 {
(parent + 1) * 2
}
}
C++ 解法, 执行用时: 24ms, 内存消耗: 13640KB, 提交时间: 2022-06-25
static const auto io_sync_off = [](){
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int qs(vector<int>& a,int l,int r,int k)
{
if(l>=r)
return a[l];
int i=l-1,j=r+1,m=a[(l+r)/2];
while(i<j)
{
do i ++ ;
while (a[i] < m);
do j -- ;
while (a[j] > m);
if(i<j)
swap(a[i],a[j]);
}
if(j-l+1>=k)
return qs(a,l,j,k);
else return qs(a,j+1,r,k-(j-l+1));
}
int findKth(vector<int> a, int n, int K) {
// write code here
return qs(a,0,n-1,n-K+1);
}
};
C++ 解法, 执行用时: 25ms, 内存消耗: 12808KB, 提交时间: 2022-06-07
static const auto io_sync_off = [](){
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int qs(vector<int>& a,int l,int r,int k)
{
if(l>=r)
return a[l];
int i=l-1,j=r+1,m=a[(l+r)/2];
while(i<j)
{
do i ++ ;
while (a[i] < m);
do j -- ;
while (a[j] > m);
if(i<j)
swap(a[i],a[j]);
}
if(j-l+1>=k)
return qs(a,l,j,k);
else return qs(a,j+1,r,k-(j-l+1));
}
int findKth(vector<int> a, int n, int K) {
// write code here
return qs(a,0,n-1,n-K+1);
}
};
C++ 解法, 执行用时: 25ms, 内存消耗: 12812KB, 提交时间: 2022-05-21
static const auto io_sync_off = [](){
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int qs(vector<int>& a,int l,int r,int k)
{
if(l>=r)
return a[l];
int i=l-1,j=r+1,m=a[(l+r)/2];
while(i<j)
{
do i ++ ;
while (a[i] < m);
do j -- ;
while (a[j] > m);
if(i<j)
swap(a[i],a[j]);
}
if(j-l+1>=k)
return qs(a,l,j,k);
else return qs(a,j+1,r,k-(j-l+1));
}
int findKth(vector<int> a, int n, int K) {
// write code here
return qs(a,0,n-1,n-K+1);
}
};