数组中的第k个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

代码3 —— 使用快排中的分治思想
重点在于 partition 函数，通过 partition 操作来定位数组中索引为 k - 1 的元素。
在主函数中，需要不断调整分治的位置，直到 position = k - 1 。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return getTopK(nums, k);
    }

    // 分治
    public int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] <= pivot) {
                high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] >= pivot) {
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }
// 为什么 要左大 右小，就是为了方便利用index==k-1这个条件
    // 获得 Kth 的数
    public int getTopK(int[] nums, int k) {
        int low = 0;
        int high = nums.length - 1;
        // 不断调整分治的位置，直到 position = k - 1
        while (true) {
            int index = partition(nums, low, high);
            if (index == k - 1) {
                return nums[index];
            }
            else if (index < k - 1) {
                low = index + 1;
            }
            else {
                high = index - 1;
            }
        }
    }
}