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}`);