编辑代码

/* 随机区间[min, max] */
function rand(min: number, max: number): number {
    return Math.trunc(Math.random() * (max - min + 1) + min);
}

/* 交换两数 */
function swap(arr: number[], x: number, y: number) {
    let temp: number = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

/**
 * @brief 快速选择
 * @param arr 
 * @param left 
 * @param right 
 * @param k 
 * @returns 
 */
function quickSelect(arr: number[], left: number, right: number, k: number): number {
    if (left >= right) return arr[left];
    swap(arr, left, rand(left, right));
    let privot: number = arr[left];
    let mark: number = left;
    for (let i: number = left + 1; i <= right; i++) {
        if (arr[i] < privot) {
            mark++;
            swap(arr, mark, i);
        }
    }
    swap(arr, mark, left);

    if (mark + 1 == k) {
        return arr[mark];
    } else if (mark + 1 > k) {
        return quickSelect(arr, left, mark - 1, k);
    } else {
        return quickSelect(arr, mark + 1, right, k);
    }
}

/**
 * @brief 查找数组第k大的值
 * @param arr
 * @param left
 * @param right
 * @param k
 * @returns
 */
function findKthLargest(arr: number[], left: number, right: number, k: number): number {
    return quickSelect(arr, left, right, k);
}

const arr: number[] = [4, 5, 1, 3, 2, 8, 6, 7];
const left: number = 0;
const right: number = arr.length - 1;
const k1 = 1;
const k2 = 5;
const k3 = 8;
const result1 = findKthLargest(arr, left, right, arr.length - k1 + 1);
const result2 = findKthLargest(arr, left, right, arr.length - k2 + 1);
const result3 = findKthLargest(arr, left, right, arr.length - k3 + 1);
console.log(result1);
console.log(result2);
console.log(result3);