数组中的第 K 个最大元素

问题

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。要求时间复杂度为 $O(n)$。

示例：

输入：nums = [3,2,1,5,6,4], k = 2
输出：5

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4

来源：LeetCode 215. 数组中的第 K 个最大元素

答案

方法一：快速选择（推荐，平均 $O(n)$）

核心思路：借鉴快速排序的 partition 思想，但只递归一侧。

findKthLargest.ts

function findKthLargest(nums: number[], k: number): number {
  // 第 k 大 = 排序后索引为 nums.length - k
  const targetIndex = nums.length - k;
  return quickSelect(nums, 0, nums.length - 1, targetIndex);
}

function quickSelect(nums: number[], left: number, right: number, target: number): number {
  if (left === right) return nums[left];

  // 随机选取 pivot，避免最坏情况
  const randomIdx = left + Math.floor(Math.random() * (right - left + 1));
  [nums[randomIdx], nums[right]] = [nums[right], nums[randomIdx]];

  const pivotIdx = partition(nums, left, right);

  if (pivotIdx === target) {
    return nums[pivotIdx];
  } else if (pivotIdx < target) {
    return quickSelect(nums, pivotIdx + 1, right, target);
  } else {
    return quickSelect(nums, left, pivotIdx - 1, target);
  }
}

function partition(nums: number[], left: number, right: number): number {
  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; // pivot 的最终位置
}

图解：

nums = [3,2,1,5,6,4], k = 2
targetIndex = 6 - 2 = 4（第 4 大 = 排序后下标 4）

假设选 pivot = 4:
  partition → [3,2,1, 4, 6,5]  pivot 在 index=3
  3 < 4 → 只看右半部分 [6, 5]

假设选 pivot = 5:
  partition → [5, 6]  pivot 在 index=4
  index=4 = target → 返回 5 ✓

复杂度分析

• 平均时间复杂度：$O(n)$ — 每次约排除一半元素：$n + n/2 + n/4 + ... = 2n$
• 最坏时间复杂度：$O(n^2)$ — 每次 pivot 选到最值（随机化可大幅降低概率）
• 空间复杂度：$O(\log n)$ — 递归栈

面试提示

一定要提随机选择 pivot！没有随机化的快速选择很容易被特殊用例卡到 $O(n^2)$。

---

方法二：最小堆（稳定 $O(n \log k)$）

维护一个大小为 k 的最小堆，堆顶就是第 k 大元素：

findKthLargestHeap.ts

function findKthLargest(nums: number[], k: number): number {
  // JS 没有内置堆，用数组模拟最小堆
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    // 上浮
    let i = heap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[parent] <= heap[i]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      // 下沉
      let i = 0;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
        if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
        if (smallest === i) break;
        [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
        i = smallest;
      }
    }
    return top;
  }

  for (const num of nums) {
    push(num);
    if (heap.length > k) {
      pop(); // 弹出最小的，保留 k 个最大的
    }
  }

  return heap[0]; // 堆顶就是第 k 大
}

复杂度分析

• 时间复杂度：$O(n \log k)$ — n 个元素，每次堆操作 $O(\log k)$
• 空间复杂度：$O(k)$ — 堆大小

---

方法三：排序（简单但不是最优）

findKthLargestSort.ts

function findKthLargest(nums: number[], k: number): number {
  nums.sort((a, b) => b - a);
  return nums[k - 1];
}

时间 $O(n \log n)$，空间 $O(\log n)$。面试中可以先写出来，再优化。

---

三种方法对比

方法	平均时间	最坏时间	空间	适用场景
快速选择	$O(n)$	$O(n^2)$	$O(\log n)$	一次性查询
最小堆	$O(n \log k)$	$O(n \log k)$	$O(k)$	数据流、k 较小
排序	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	简单场景

---

常见面试追问

Q1: 如果数据是流式的（不断有新数据进来）？(LeetCode 703)

答案：用最小堆，维护 k 个最大的元素：

class KthLargest {
  private heap: number[] = [];
  private k: number;

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const num of nums) this.add(num);
  }

  add(val: number): number {
    // 简化：直接 push + sort（面试中可用堆优化）
    this.heap.push(val);
    this.heap.sort((a, b) => a - b);
    while (this.heap.length > this.k) this.heap.shift();
    return this.heap[0];
  }
}

Q2: 快速选择和快速排序的区别？

答案：

	快速排序	快速选择
递归	两侧都递归	只递归一侧
时间	$O(n \log n)$	$O(n)$
目的	完全排序	只找第 k 个

Q3: 前端 Top K 场景？

答案：

• 搜索热词：Top 10 热门搜索
• 性能监控：找出最慢的 K 个接口
• 日志分析：出现频率最高的 K 种错误

相关链接

• LeetCode 215. 数组中的第 K 个最大元素
• LeetCode 347. 前 K 个高频元素
• LeetCode 703. 数据流中的第 K 大元素
• 排序算法