0215.数组中的第K个最大元素
难度：🟡 中等
标签：数组、分治、快速选择、排序、堆
题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
解题思路
核心思想
本题的目标是在一个未排序的数组中，找到第 k 大的元素。一个直观的方法是对数组完全排序然后取倒数第 k 个元素，但其时间复杂度为 O(n log n)，不符合题目要求。要实现 O(n) 的时间复杂度，我们需要更高效的算法。
思路选择
快速选择算法 (Quickselect) 是解决此问题的标准最优思路。
快速选择算法是快速排序算法的一个变种。快速排序的核心是“分区”操作，它会选择一个“枢轴”(pivot) 并将数组分为两部分：小于枢轴的元素和大于枢轴的元素。分区操作结束后，枢轴元素就位于其最终排序后的正确位置上。
我们利用这个特性。每次分区后，我们检查枢轴的索引
j。如果
j恰好等于我们想找的索引（第k大的元素，其索引为n-k），那么我们就找到了答案。如果
j大于目标索引，说明第k大的元素在枢轴的左边，我们只需在左半部分递归地继续查找。如果
j小于目标索引，说明第k大的元素在枢轴的右边，我们只需在右半部分递归地继续查找。
由于每次都只处理其中一半的数组，其平均时间复杂度可以达到 O(n)。
关键步骤
问题转换：将寻找“第
k大”的元素，转换为寻找“第n-k小”的元素（按索引从 0 开始算）。定义快速选择函数
quickselect(nums, left, right, targetIndex)： a. 在[left, right]区间内，选择一个枢轴（例如nums[left]）。 b. 执行一次分区操作，使得所有小于枢轴的元素在左边，大于枢轴的元素在右边，返回枢轴最终的索引j。 c. 判断与递归： i. 如果targetIndex === j，返回nums[j]。 ii. 如果targetIndex < j，在左半部分[left, j-1]递归调用quickselect。 iii. 如果targetIndex > j，在右半部分[j+1, right]递归调用quickselect。
代码实现
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
const n = nums.length;
// 寻找第 k 大的元素，等价于寻找第 n-k 小的元素（索引从0开始）
return quickselect(nums, 0, n - 1, n - k);
};
/**
* 快速选择辅助函数
* @param {number[]} nums - 输入数组
* @param {number} left - 当前搜索范围的左边界
* @param {number} right - 当前搜索范围的右边界
* @param {number} targetIndex - 目标元素的索引
* @return {number}
*/
function quickselect(nums, left, right, targetIndex) {
// 递归终止条件：当分区大小为1时，直接返回该元素
if (left === right) return nums[left];
// 选择第一个元素作为枢轴
const pivotValue = nums[left];
let i = left - 1, j = right + 1;
// 快速排序的划分过程
while (i < j) {
// 从左向右找到第一个大于等于枢轴的元素
do i++; while (nums[i] < pivotValue);
// 从右向左找到第一个小于等于枢轴的元素
do j--; while (nums[j] > pivotValue);
// 交换这两个元素
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
// 递归查找：根据枢轴的位置 j，决定在哪一半区间继续搜索
if (targetIndex <= j) {
return quickselect(nums, left, j, targetIndex);
} else {
return quickselect(nums, j + 1, right, targetIndex);
}
}
复杂度分析
时间复杂度：平均 O(n)，最坏 O(n²) 平均情况下，每次分区操作都能将问题规模减半，总时间复杂度为
n + n/2 + n/4 + ... = 2n，即 O(n)。最坏情况下（每次都选到最大或最小的元素作为枢轴），算法退化为 O(n²)。空间复杂度：平均 O(log n)，最坏 O(n) 空间消耗主要来自递归调用栈。
相关题目
总结
本题是“Top K”问题的经典范例。虽然排序后取值或使用堆（优先队列）也能解决，但快速选择算法提供了一个平均时间复杂度为 O(n) 的高效解法。它充分利用了快排的分区思想，通过“减治法”不断缩小问题规模，是面试中考察算法基本功和优化能力的高频题。