编辑代码

function quickSelect(nums, k) {
    if (!nums || k <= 0 || k > nums.length) {
        return null;
    }

    return _quickSelect(nums, 0, nums.length - 1, k);
}

function _quickSelect(nums, left, right, k) {
    // 随机选择枢纽元素的位置
    const pivotIndex = randomPartition(nums, left, right);

    if (pivotIndex === k - 1) {
        return nums[pivotIndex];
    } else if (pivotIndex < k - 1) {
        return _quickSelect(nums, pivotIndex + 1, right, k);
    } else {
        return _quickSelect(nums, left, pivotIndex - 1, k);
    }
}

function randomPartition(nums, left, right) {
    // 随机选择枢纽元素
    const pivotIndex = Math.floor(Math.random() * (right - left + 1) + left);
    // 将枢纽元素交换到数组末尾
    [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];

    return partition(nums, left, right);
}

function partition(nums, left, right) {
    // 使用枢纽元素进行分区
    const pivot = nums[right];
    let i = left - 1;

    for (let j = left; j < right; j++) {
        if (nums[j] >= pivot) {
            i++;
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }

    [nums[i + 1], nums[right]] = [nums[right], nums[i + 1]];
    return i + 1;
}

// 示例
const arr = [3, 1, 4, 4, 2, 2, 5, 3, 9];
const k = 2;
const result = quickSelect(arr, k);
console.log(`第${k}大的是 ${result}`);

const k3 = 3;
const result3 = quickSelect(arr, k3);
console.log(`第${k3}大的是 ${result3}`);