解析 LeetCode 第 215 题“数组中的第 K 个最大元素”。主要介绍两种解法：快速选择算法和堆排序。快速选择平均时间复杂度为 O(n)，满足题目要求，是最优解；堆排序时间复杂度为 O(nlogn)，适用于面试或动态数据流场景。文章包含 Java 代码实现、复杂度分析、随机化优化策略及实际应用场景（如 Top-K 推荐系统）。通过分治思想和双指针划分，帮助读者掌握线性时间选择算法的核心逻辑。
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入：[3,2,1,5,6,4], k = 2
输出：5
解释：排序后为 [1,2,3,4,5,6]，第 2 大的元素是 5。
示例 2:
输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4
解释：排序后为 [1,2,2,3,3,4,5,5,6]，第 4 大的元素是 4（注意重复元素也要计算）。
1 ≤ k ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4我们需要在未排序的数组中找到第 k 大的元素，等价于找到排序后索引为 n-k 的元素（0-based）。
Arrays.sort()）；nums[n - k]。时间复杂度：O(n log n)
空间复杂度：O(1)（原地排序）
问题：题目要求 O(n) 时间复杂度，此法不满足。
时间复杂度：O(n log k)
空间复杂度：O(k)
问题：当 k≈n 时，退化为 O(n log n)，仍不满足 O(n) 要求。
关键洞察：我们需要一种线性时间的选择算法，而非完全排序。
快速选择（Quickselect） 是快速排序的变种，专用于解决'第 k 小/大元素'问题。
基本思路：
k-1 次删除操作；class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
// 第 k 大 = 索引为 n-k 的元素（0-based）
return quickselect(nums, 0, n - 1, n - k);
}
private int quickselect(int[] nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
// 选择主元（这里用 left，实际可随机化）
int pivot = nums[left];
int i = left - 1;
int j = right + 1;
// 双指针划分：左边 <= pivot，右边 >= pivot
while (i < j) {
do i++;
while (nums[i] < pivot);
do j--;
while (nums[j] > pivot);
if (i < j) {
swap(nums, i, j);
}
}
// j 是左部分的最后一个索引
if (k <= j) {
return quickselect(nums, left, j, k);
} else {
return quickselect(nums, j + 1, right, k);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
// 建大根堆
buildMaxHeap(nums, heapSize);
// 执行 k-1 次删除（将最大元素移到末尾）
for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(nums, 0, i);
heapSize--;
maxHeapify(nums, 0, heapSize);
}
return nums[0]; // 堆顶即为第 k 大
}
// 建堆：从最后一个非叶子节点开始调整
private void buildMaxHeap(int[] nums, int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; i--) {
maxHeapify(nums, i, heapSize);
}
}
// 堆调整：维护大根堆性质
private void maxHeapify(int[] nums, int i, int heapSize) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < heapSize && nums[left] > nums[largest]) {
largest = left;
}
if (right < heapSize && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums, i, largest);
maxHeapify(nums, largest, heapSize);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
快速选择更优（满足 O(n) 要求），堆排序作为备选（面试常考）。
q；k <= q → 在左部分查找；i 从左向右找 ≥ pivot 的元素；j 从右向左找 ≤ pivot 的元素；i >= j。n/2 - 1 开始（最后一个非叶子节点）；[3,2,1,5,6,4], k=2 为例）6-2 = 4 的元素；left=0, right=5, k=4；[2,1,3,5,6,4]，j=2；k=4 > j=2，递归右部分 [5,6,4]；nums[4] = 5。[6,5,4,3,2,1]；maxHeapify 递归栈。结论：快速选择是本题的最佳解法（满足 O(n) 要求）。
答：假设每次划分将数组分为 1:1，则：第 1 层：n 次比较；第 2 层：n/2 次；第 3 层：n/4 次；总计：n + n/2 + n/4 + ... = 2n = O(n)。
答：随机选择主元。
答：可以，但时间复杂度为 O(n log k)，不满足题目 O(n) 要求。
答：虽然建堆是 O(n)，但我们需要执行 k-1 次删除操作，每次 O(log n)。当 k=n 时，总时间为 O(n log n)。
private int quickselect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
// 随机选择主元
Random rand = new Random();
int randomIndex = left + rand.nextInt(right - left + 1);
swap(nums, left, randomIndex);
int pivot = nums[left];
// ... 其余代码不变
}
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int target = n - k;
int left = 0, right = n - 1;
while (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == target) {
return nums[pivotIndex];
} else if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return nums[left];
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int i = left - 1, j = right + 1;
while (i < j) {
do i++;
while (nums[i] < pivot);
do j--;
while (nums[j] > pivot);
if (i < j) swap(nums, i, j);
}
return j;
}
< pivot, = pivot, > pivot 三部分；insert：O(log n)extractMax/Min：O(log n)buildHeap：O(n)答：通过随机选择主元，使得最坏情况的概率极低，期望时间复杂度稳定为 O(n)。
答：只需将目标索引改为 k-1（0-based）。
答：可以！因为数据范围小（-10⁴ ~ 10⁴）：
时间复杂度：O(n + range) = O(n)，空间复杂度：O(range)。
答：堆排序更适合。因为快速选择需要全部数据，而堆可以动态维护 top-k。
答：因为大部分节点在底层，调整代价小。数学证明：高度为 h 的节点数 ≤ n/2^(h+1)；总代价 = ∑(n / 2^(h+1)) × h = O(n)。
SELECT * FROM table ORDER BY score DESC LIMIT k；本质：任何需要'Top-K'或'第 K 大/小'的场景，都可用本题算法。
| 题号 | 题目 | 关联点 |
|---|---|---|
| [215] | 数组中的第 K 个最大元素 | 本题 |
| [347] | 前 K 个高频元素 | 堆/桶排序 |
| [451] | 根据字符出现频率排序 | 堆 |
| [692] | 前 K 个高频单词 | 堆 + 自定义比较器 |
| [703] | 数据流中的第 K 大元素 | 堆（动态） |
| [973] | 最接近原点的 K 个点 | 快速选择/堆 |
| [1471] | 数组中的 k 个最强值 | 快速选择 |
重点练习：LeetCode 703：动态数据流，必须用堆；LeetCode 973：自定义比较规则，快速选择更优。
PriorityQueue）。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online