LeetCode 215. 数组中的第 K 个最大元素
题目核心
给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。
这里求的是排序后第 k 个位置上的元素，而不是第 k 个不同的元素。重复数字需要正常计数。
例如：
nums = [3, 2, 1, 5, 6, 4], k = 2
降序排列后：[6, 5, 4, 3, 2, 1]
答案：5解题思考过程
第一步：理解问题
求第 k 个最大元素，等价于求第 n-k+1 个最小元素（n是数组长度）。
第二步：暴力解法（排序）
最直接的思路：把数组排序，然后取第 k 个元素。
nums.sort((a,b) => b-a)
return nums[k-1]
时间复杂度：O(n log n)
空间复杂度：O(1) 或 O(n)这个思路简单，但排序需要 O(n log n)，能不能更快？
第三步：想到堆
可以用小顶堆，只维护 k 个最大的元素：
1. 遍历数组，把元素加入堆
2. 如果堆大小 > k，弹出最小的元素
3. 遍历结束后，堆顶就是第 k 个最大元素
时间复杂度：O(n log k)
空间复杂度：O(k)当 k 远小于 n 时，这个方法比排序快。
第四步：想到快速选择
快速排序的思想是分治：选择一个 pivot，把数组分成两部分，左边 <= pivot，右边 >= pivot。
如果 pivot 的位置正好是 n-k，那它就是答案！
快速选择：
1. 选择 pivot
2. 分区：左边 <= pivot，右边 >= pivot
3. 如果 pivot 位置 == n-k，返回 pivot
4. 如果 pivot 位置 < n-k，递归右边
5. 如果 pivot 位置 > n-k，递归左边
平均时间复杂度：O(n)
最坏时间复杂度：O(n²)第五步：计数数组（特殊解法）
题目中数值范围有限（-10^4 到 10^4），可以用计数数组：
1. 创建计数数组，统计每个数字出现的次数
2. 从大到小遍历计数数组，累加计数
3. 当累加和 >= k 时，当前数字就是答案
时间复杂度：O(n + m) - m是数值范围
空间复杂度：O(m)这个方法只适用于数值范围有限的情况。
第六步：方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 排序 | O(n log n) | O(1) | 通用 |
| 堆 | O(n log k) | O(k) | k 较小 |
| 快速选择 | O(n) 平均 | O(1) | 通用，期望最优 |
| 计数数组 | O(n + m) | O(m) | 数值范围有限 |
快速选择是平均最优的方法。
当前解法：计数数组
当前代码利用题目中数值范围有限的条件，为每个可能的数字统计出现次数。
因为数字可能为负数，所以使用偏移量把数字映射到非负下标：
const OFFSET = 10000;
const count = new Array(20001).fill(0);
for (const num of nums) {
count[num + OFFSET]++;
}映射关系如下：
原数字 -10000 -> 下标 0
原数字 0 -> 下标 10000
原数字 10000 -> 下标 20000统计完成后，从最大的下标向最小的下标遍历，并累加出现次数：
let sum = 0;
for (let i = count.length - 1; i >= 0; i--) {
sum += count[i];
if (sum >= k) {
return i - OFFSET;
}
}第一次满足 sum >= k 时，当前数字就是第 k 大元素。
完整代码
var findKthLargest = function (nums, k) {
const OFFSET = 10000;
const count = new Array(20001).fill(0);
for (const num of nums) {
count[num + OFFSET]++;
}
let sum = 0;
for (let i = count.length - 1; i >= 0; i--) {
sum += count[i];
if (sum >= k) {
return i - OFFSET;
}
}
return -1;
};代码逐行解释
var findKthLargest = function (nums, k) {定义函数，参数 nums 是数组，k 是要求的第 k 大元素。
const OFFSET = 10000;偏移量 OFFSET 用于将负数映射到非负下标。因为题目中数字范围是 -10000 到 10000，加上 10000 后，范围变成 0 到 20000。
const count = new Array(20001).fill(0);创建计数数组，长度为 20001，覆盖 0 到 20000 的所有下标。
for (const num of nums) {
count[num + OFFSET]++;
}遍历数组，对每个数字进行计数。num + OFFSET 将原数字转换为数组下标，count[index]++ 表示该数字出现次数加 1。
let sum = 0;sum 用于累计已经统计过的数字总个数。
for (let i = count.length - 1; i >= 0; i--) {从最大的下标开始向左遍历（即从最大的数字开始向最小的数字遍历）。
sum += count[i];累加当前数字的出现次数到 sum 中。
if (sum >= k) {
return i - OFFSET;
}如果累计个数已经达到或超过 k，说明当前数字就是第 k 大元素。i - OFFSET 将下标转换回原数字。
}
return -1;
};如果没有找到（理论上不会发生），返回 -1。
为什么重复数字要累加次数
例如：
nums = [5, 5, 4], k = 2数字 5 出现两次，所以扫描到 5 时累计数量直接变为 2。排序后前两个位置都是 5，第 2 大元素仍然是 5。
因此不能只记录某个数字是否出现，必须记录它的完整出现次数。
执行过程示例
以 nums = [3, 2, 1, 5, 6, 4], k = 2 为例：
count[3+10000] = 1 → count[10003] = 1
count[2+10000] = 1 → count[10002] = 1
count[1+10000] = 1 → count[10001] = 1
count[5+10000] = 1 → count[10005] = 1
count[6+10000] = 1 → count[10006] = 1
count[4+10000] = 1 → count[10004] = 1
从后向前扫描：
i = 20000, count[20000] = 0, sum = 0
...
i = 10006, count[10006] = 1, sum = 1 (数字 6)
i = 10005, count[10005] = 1, sum = 2 >= k=2 → 返回 10005 - 10000 = 5
答案：5复杂度
设数组长度为 n，数值范围大小为 R：
- 时间复杂度：
O(n + R)。 - 空间复杂度：
O(R)。
当前实现中 R = 20001，是固定大小，因此在本题约束下，时间复杂度可以视为 O(n)，额外空间也可以视为常数空间。
这种写法依赖明确的数值范围。如果输入可能远小于 -10000 或远大于 10000，就不能直接使用当前固定大小的数组。
替代解法一：排序
最直接的方法是把数组按降序排列，再返回下标 k - 1 的元素：
var findKthLargest = function (nums, k) {
nums.sort((a, b) => b - a);
return nums[k - 1];
};排序解法逐行解释
var findKthLargest = function (nums, k) {定义函数。
nums.sort((a, b) => b - a);按降序排序数组。(a, b) => b - a 表示当 b > a 时，b 排在前面。
return nums[k - 1];
};返回排序后第 k 个元素（下标为 k - 1）。
- 时间复杂度：
O(n log n)。 - 空间复杂度：取决于 JavaScript 引擎的排序实现。
排序写法简单，但它处理了完整的排序关系，而题目实际上只需要找到一个位置。
替代解法二：快速选择
快速选择基于快速排序的分区操作。每次分区后，只继续处理第 k 大元素所在的一侧，不需要对整个数组排序。
var findKthLargest = function (nums, k) {
const target = nums.length - k;
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const pivotIndex = partition(nums, left, right);
if (pivotIndex === target) {
return nums[pivotIndex];
}
if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
};
function partition(nums, left, right) {
const pivot = nums[right];
let boundary = left;
for (let i = left; i < right; i++) {
if (nums[i] <= pivot) {
[nums[i], nums[boundary]] = [nums[boundary], nums[i]];
boundary++;
}
}
[nums[boundary], nums[right]] = [nums[right], nums[boundary]];
return boundary;
}快速选择代码逐行解释
var findKthLargest = function (nums, k) {定义函数。
const target = nums.length - k;将第 k 大转换为第 target 小。例如数组长度为 6，第 2 大就是第 6 - 2 = 4 小。
let left = 0;
let right = nums.length - 1;初始化左右指针，覆盖整个数组。
while (left <= right) {循环条件：只要左右指针没有交错，就继续查找。
const pivotIndex = partition(nums, left, right);调用分区函数，返回基准值最终所在的下标。
if (pivotIndex === target) {
return nums[pivotIndex];
}如果基准值刚好在目标位置，直接返回。
if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}如果基准值在目标位置左边，说明目标在右侧，移动左指针；否则移动右指针。
function partition(nums, left, right) {分区函数，将数组分成两部分：左边小于等于基准值，右边大于基准值。
const pivot = nums[right];选择最右边的元素作为基准值。
let boundary = left;boundary 是小于等于基准值区域的右边界。
for (let i = left; i < right; i++) {
if (nums[i] <= pivot) {
[nums[i], nums[boundary]] = [nums[boundary], nums[i]];
boundary++;
}
}遍历数组，将小于等于基准值的元素交换到 boundary 左侧，并扩展 boundary。
[nums[boundary], nums[right]] = [nums[right], nums[boundary]];
return boundary;将基准值交换到正确的位置（boundary），返回基准值下标。
快速选择的平均时间复杂度为 O(n)，最坏时间复杂度为 O(n²)。通过随机选择基准值，可以降低连续遇到最坏分区的概率。
解法选择
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 计数数组 | O(n + R) | O(R) | 数值范围较小且明确 |
| 排序 | O(n log n) | 取决于实现 | 代码最简单，数据规模不大 |
| 快速选择 | 平均 O(n) | 通常 O(1) | 数值范围很大，只需要第 k 大 |
当前题目给出了适合计数的数值范围，所以当前的方案直接且高效。