传送门
代码
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums,0,nums.length - 1,nums.length - k);
}
public int quickSelect(int[] a,int l,int r,int k) {
if(l >= r) return a[l];
int base = a[l + r >> 1];
int i = l - 1,j = r + 1;
while(i < j) {
do i ++;while(a[i] < base);
do j --;while(a[j] > base);
if(i < j) swap(a,i,j);
}
if(k <= j) return quickSelect(a,l,j,k);
else return quickSelect(a,j + 1,r,k);
}
public void swap(int[] a,int l,int r) {
int t = a[l];
a[l] = a[r];
a[r] = t;
}
}
思路
快速选择算法
时间复杂度 \(O(n)\)
参考快排的思路,但是每次只选择一边进行递归,不会把两边都递归
题目要求,第 k 大,也就是把数组排序后(下标从 0 开始),第 n - k 小的数
每次直接把数组以 base 为中心(这个 base 可以用 random 来取,可以防止被卡)切分成两半
然后把整个数组重新整理,拨开到两边,那么这样的话 base 所在的位置,就一定是排好序后,它下标的位置
最后 i j 退出循环的时候,一定在 base 的分界线处
所以,如果要求的下标 k 在左边,就继续递归左边\([l,j]\),否则就递归右边\([j + 1,r]\)
不断夹逼,就会找到在下标为 k 的数