题解 | #寻找第K大#

function findKth(a, n, K) {
    function quickSelect(arr, left, right, K) {
        if (left === right) return arr[left];

        let pivotIndex = partition(arr, left, right);

        if (K === pivotIndex) {
            return arr[K];
        } else if (K < pivotIndex) {
            return quickSelect(arr, left, pivotIndex - 1, K);
        } else {
            return quickSelect(arr, pivotIndex + 1, right, K);
        }
    }

    function partition(arr, left, right) {
        let pivot = arr[right];
        let i = left;

        for (let j = left; j < right; j++) {
            if (arr[j] > pivot) {
                // 对于找第 K 大的元素，用大于号
                [arr[i], arr[j]] = [arr[j], arr[i]];
                i++;
            }
        }
        [arr[i], arr[right]] = [arr[right], arr[i]];
        return i;
    }

    return quickSelect(a, 0, n - 1, K - 1);
}
module.exports = {
    findKth: findKth,
};