class Solution {
    public int findKthLargest(int[] nums, int k) {
        // n：记录数组的总长度
        int n = nums.length;
        // 第 k 大的元素，在升序排序后的数组中，对应的索引实际上是 n - k
        return help(nums, 0, n - 1, n - k);
    }

    // help：快速选择算法的辅助递归函数
    // nums：原数组；l：当前分区的左边界；r：当前分区的右边界；k：全局升序索引目标
    public int help(int[] nums, int l, int r, int k) {
        // 递归终止条件：如果区间内只有一个元素，那么这个元素就是我们要找的答案
        if (l == r) return nums[r];
        
        // x：选取当前区间最左侧的元素作为基准值（Pivot）
        int x = nums[l];
        // i：左侧扫描指针，初始化为 l - 1，用于配合 do-while 循环
        int i = l - 1;
        // j：右侧扫描指针，初始化为 r + 1，用于配合 do-while 循环
        int j = r + 1;
        
        // 开始 Hoare 分区过程，只要 i < j 就继续扫描
        while (i < j) {
            // 左指针向右移动，直到找到一个大于等于基准值 x 的元素
            do {
                i++;
            } while (nums[i] < x);
            
            // 右指针向左移动，直到找到一个小于等于基准值 x 的元素
            do {
                j--;
            } while (nums[j] > x);
            
            // 如果左右指针还没有相遇，则交换这两个不满足分区条件的元素
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        
        // 分区结束后，右指针 j 及其左侧的元素都是小于等于基准值的部分。
        // 判断目标索引 k 落在基准值 j 的左侧还是右侧
        if (k <= j) {
            // 如果 k 在 j 的左侧（包含 j），递归搜索左半区 [l, j]
            return help(nums, l, j, k);
        } else {
            // 如果 k 在 j 的右侧，递归搜索右半区 [j + 1, r]
            return help(nums, j + 1, r, k);
        }
    }
}