数组中的第 K 个最大元素

function findKthLargest(nums, k) {
    // 第K大 = 排序后索引 length - k
    let target = nums.length - k;
    return quickSelect(nums, 0, nums.length - 1, target);
}


function quickSelect(nums, left, right, target) {
    if (left === right) return nums[left];
    
    // 进行分区，返回 pivot 的最终索引
    let pIndex = partition(nums, left, right);
    
    if (target === pIndex) {
        return nums[pIndex];
    } else if (target < pIndex) {
        return quickSelect(nums, left, pIndex - 1, target);
    } else {
        return quickSelect(nums, pIndex + 1, right, target);
    }
}


function partition(nums, left, right) {
    let pivot = nums[right];
    let storeIndex = left;
    
    for (let i = left; i < right; i++) {
        if (nums[i] <= pivot) {
            swap(nums, storeIndex, i);
            storeIndex++;
        }
    }
    swap(nums, storeIndex, right);
    return storeIndex;
}