数组中第 K 大的元素怎样找？小顶堆和快速选择的复杂度有什么区别？
小顶堆的做法是维护一个大小为 k 的最小堆，遍历时把每个数放进去，超过 k 个就弹出堆顶，最后堆顶就是第 k 大，时间 O(n log k)、空间 O(k)。快速选择借用快速排序的分区，每次只往答案所在的一侧递归，平均 O(n)，最坏 O(n²)，随机选基准可以避免固定输入总落到最坏情况。
简答
第 K 大的元素，是把数组从大到小排好后排在第 k 位的那个数，重复的数各算一次，
[3,2,3,1,2,4,5,5,6]里第 4 大是 4。最直接的做法是排序后取下标n - k，时间 O(n log n)，题目希望不靠完整排序来做。小顶堆的做法像只保留前 k 名的排行榜：堆里最多放 k 个数，堆顶是这 k 个里最小的。每来一个数就放进去，超过 k 个就把堆顶这个最小的踢掉。遍历完，堆里是最大的 k 个数，堆顶就是第 k 大。每次进出堆 O(log k)，总共 O(n log k)，空间 O(k)。
快速选择借用快速排序的分区：选一个基准，把比它小的放左边、大的放右边，基准落到的下标就是它排好序后的位置。如果正好是
n - k就找到了，否则只往答案所在的那一侧继续，另一侧直接丢掉。每轮平均扔掉一半，总共平均 O(n)。要注意，快速选择最坏是 O(n²)，基准总选到最大或最小值时每轮只排除一个数，所以基准要随机选。它还会原地打乱数组。堆的做法适合数据流式到达、内存只放得下 k 个的情况；快速选择适合数组已经在内存里、只求一次的情况。
两种写法
MinHeap 只写了用得到的方法，push 往上浮、pop 往下沉。快速选择用的是 Lomuto 分区，看 quickSelect 里怎样根据基准的位置决定往哪边走。
class MinHeap {
constructor() {
this.items = [];
}
get size() {
return this.items.length;
}
peek() {
return this.items[0];
}
push(value) {
const a = this.items;
a.push(value);
let i = a.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (a[parent] <= a[i]) break;
[a[parent], a[i]] = [a[i], a[parent]];
i = parent;
}
}
pop() {
const a = this.items;
const top = a[0];
const last = a.pop();
if (a.length) {
a[0] = last;
let i = 0;
while (true) {
let smallest = i;
for (const child of [2 * i + 1, 2 * i + 2]) {
if (child < a.length && a[child] < a[smallest]) smallest = child;
}
if (smallest === i) break;
[a[smallest], a[i]] = [a[i], a[smallest]];
i = smallest;
}
}
return top;
}
}
function findKthLargestByHeap(nums, k) {
const heap = new MinHeap();
for (const num of nums) {
heap.push(num);
if (heap.size > k) heap.pop();
}
return heap.peek();
}
function partition(a, lo, hi) {
const r = lo + Math.floor(Math.random() * (hi - lo + 1));
[a[r], a[hi]] = [a[hi], a[r]];
const pivot = a[hi];
let store = lo;
for (let i = lo; i < hi; i++) {
if (a[i] < pivot) {
[a[i], a[store]] = [a[store], a[i]];
store++;
}
}
[a[store], a[hi]] = [a[hi], a[store]];
return store;
}
function findKthLargestByQuickSelect(nums, k) {
const a = [...nums];
const target = a.length - k;
let lo = 0;
let hi = a.length - 1;
while (true) {
const p = partition(a, lo, hi);
if (p === target) return a[p];
if (p < target) lo = p + 1;
else hi = p - 1;
}
}
console.log(findKthLargestByHeap([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargestByHeap([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4
console.log(findKthLargestByQuickSelect([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargestByQuickSelect([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4
console.log(findKthLargestByQuickSelect([7], 1)); // 7
为什么找第 k 大要用小顶堆，不是大顶堆？堆里要留下的是最大的 k 个数，需要随时踢掉的是这 k 个里最小的那个，小顶堆的堆顶正好就是它，O(1) 能看到，O(log k) 能删掉。用大顶堆也能做，但要把 n 个数全放进去再弹 k − 1 次，空间是 O(n)。
快速选择里 target = a.length - k 是怎么来的？从小到大排好序后，第 1 大在下标 n - 1，第 k 大在下标 n - k。partition 返回基准最终的下标，它左边都比它小，右边都不小于它，所以它就在排好序以后的位置上。基准下标比目标小，答案只能在右边；比目标大，答案只能在左边。
示例里的快速选择用了 Math.random，每次运行分区的过程不同，但返回的值是确定的，因为第 k 大的数只有一个值。函数先复制了数组，避免原地交换改掉调用方的数据。
复杂度从哪来
快速选择平均 O(n) 是这么算的：基准随机时，每轮平均能把范围缩小到原来的一半左右，各轮的扫描量是 n、n/2、n/4……加起来不超过 2n。快速排序要两边都递归，每层都要扫完整个数组，所以是 O(n log n)；快速选择只走一边，省掉了这个 log。最坏情况是每轮基准都选到当前范围的最值，扫描量是 n、n − 1、n − 2……加起来 O(n²)。
还有一点：Lomuto 分区遇到大量重复值时，等于基准的数全都分到同一边，全是相同的值时会退化。处理方法是三路分区，把等于基准的数单独归为中间一段，目标下标落在这一段里就直接返回。
堆的做法时间稳定在 O(n log k)，k 很小时接近 O(n)。小顶堆的完整实现和插入、删除的过程见《前端任务怎样按优先级排队？二叉堆为什么不需要每次完整排序？》，快速排序的分区见《快速排序和归并排序怎样实现？时间复杂度和稳定性有什么区别？》。
常见追问
直接 sort 再取值可以吗？
面试里先说出来没问题，时间 O(n log n)，代码最短。要记得传比较函数，
nums.sort((a, b) => b - a)[k - 1]，因为 MDN 说明不传比较函数时sort会按字符串比较，[1, 10, 9].sort()得到的是[1, 10, 9]，不是按数值排好的[1, 9, 10]。还要注意sort会修改原数组。
要求返回前 k 大的所有元素呢？
小顶堆跑完以后，堆里剩下的就是前 k 大，只是没有排序，需要的话再排一下，O(k log k)。快速选择找到下标
n - k时，右边的部分也正好是前 k 大的数。
数据是源源不断到来的，怎么随时给出第 k 大？
用小顶堆。每来一个数就
push，超过 k 个就pop，任何时候堆顶都是目前为止的第 k 大，空间只要 O(k)。快速选择需要整个数组都在手里，不适合这种场景。