215. 数组中的第K个最大元素

参考: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;
    }


}