LeetCode 「中等」215.数组中的第K个最大元素
题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例
输入：[3,2,1,5,6,4], k = 2
输出：5
输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4
解答
无脑调用 sort 方法
Code
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
return nums.sort((a, b) => b - a)[k - 1];
};
快速选择
- 选择一个元素作为“基准”（pivot）
- 将数组分为两部分：一部分包含大于基准的元素，另一部分包含小于基准的元素
- 根据
k的值，决定在哪个部分中继续查找第k个最大的元素 - 递归地在选定的部分中重复上述步骤，直到找到第
k个最大的元素
Code
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
var partition = function (nums, left, right) {
const pivot = nums[right];
let i = left;
for (let j = left; j < right; ++j) {
if (nums[j] > pivot) {
[nums[i], nums[j]] = [nums[j], nums[i]];
++i;
}
}
[nums[i], nums[right]] = [nums[right], nums[i]];
return i;
};
var quickSelect = function(nums, left, right, k) {
if (left === right) return nums[left];
const pivotIndex = partition(nums, left, right);
if (pivotIndex === k) {
return nums[k];
} else if (pivotIndex > k) {
return quickSelect(nums, left, pivotIndex - 1, k);
} else {
return quickSelect(nums, pivotIndex + 1, right, k);
}
};
return quickSelect(nums, 0, nums.length - 1, k - 1);
};