参考:https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/19607/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
https://www.bilibili.com/video/BV1La411J7q9/?spm_id_from=333.999.0.0
class Solution {
public int findKthLargest(int[] nums, int k) {
// 第 1 大的数，下标是 len - 1;
// 第 2 大的数，下标是 len - 2;
// ...
// 第 k 大的数，下标是 len - k;
int len = nums.length;
int target = len - k;
int left = 0;
int right = len - 1;
while (true) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == target) {
return nums[pivotIndex];
} else if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
// pivotIndex > target
right = pivotIndex - 1;
}
}
}
public int partition(int[] array,int start,int end){
int base = array[start];
while (start<end){
while (start<end&&array[end]>=base) end--;
array[start] = array[end];
while (start<end&&array[start]<=base) start++;
array[end] = array[start];
}
array[start] = base;
return start;
}
}