算法篇 ｜ TopK

前言

“给你一个数组，找出第 K 大的元素”——这道题几乎是面试中最高频的算法题之一。它看起来很简单（排个序取第 K 个不就行了？），但面试官真正想考察的是：你知道几种解法？它们的时间复杂度分别是多少？什么场景下选择哪种？

TopK 问题本质上是一个选择问题（Selection Problem）：从 n 个元素中找出第 K 大（或前 K 个最大/最小）的元素。它有三种经典解法：

1. 排序法：最直观，O(n log n)
2. 快速选择算法（Quick Select）：基于快排的 partition，平均 O(n)
3. 堆（优先队列）：维护一个大小为 K 的小顶堆，O(n log k)

这三种方案各有优劣，面试中能清晰地对比分析它们是加分项。本章我们就逐一拆解，并通过经典 LeetCode 题目帮你把它们练熟。

诊断自测

Q1：从一个无序数组中找到第 K 大的元素，最优的时间复杂度是多少？用什么方法实现？

Q2：如果数据量非常大（比如 10 亿个数），找前 K 大的元素，你会用什么方法？为什么？

一、排序法

最直观的方法：先排序，然后直接取第 K 个。

function findKthLargest(nums, k) {
  nums.sort((a, b) => b - a); // 降序排序
  return nums[k - 1];
}

复杂度分析：

• 时间复杂度：O(n log n)
• 空间复杂度：O(log n)（排序的栈空间）

优点：代码极其简单，不容易出 Bug。

缺点：做了多余的工作——我们只需要第 K 大的元素，不需要把整个数组排好序。如果 K 远小于 n，这种方法效率很低。

注意：JavaScript 的 Array.prototype.sort 内部使用 Timsort 算法，时间复杂度是 O(n log n)。但面试中用排序法只能当作”保底”解法，面试官一定会追问更优的方案。

二、快速选择算法（Quick Select）

快速选择算法是快排的”半成品”——它用了快排的 partition 操作，但每次只递归一侧，所以平均时间复杂度从 O(n log n) 降到了 O(n)。

2.1 Partition 操作

Partition 的作用是：选一个基准值（pivot），把数组分成三部分——小于 pivot 的、等于 pivot 的、大于 pivot 的，并返回 pivot 的最终位置。

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

  const pivot = nums[right];
  let i = left; // i 指向"小于 pivot 的区域"的右边界

  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 的最终位置
}

2.2 Quick Select 实现

function findKthLargest(nums, k) {
  // 第 k 大 = 第 (n - k) 小（0-indexed）
  const targetIndex = nums.length - k;
  return quickSelect(nums, 0, nums.length - 1, targetIndex);
}

function quickSelect(nums, left, right, targetIndex) {
  if (left === right) return nums[left];

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

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

function partition(nums, left, right) {
  const randomIdx = left + Math.floor(Math.random() * (right - left + 1));
  [nums[randomIdx], nums[right]] = [nums[right], nums[randomIdx]];

  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;
}

为什么平均是 O(n)？

每次 partition 后，我们只递归一侧。假设每次 pivot 恰好在中间，那么递归的工作量是：

n + n/2 + n/4 + n/8 + ... ≈ 2n = O(n)

但最坏情况下（每次 pivot 都是最大或最小值），时间复杂度退化为 O(n²)。随机选取 pivot 可以有效避免最坏情况。

复杂度分析：

• 时间复杂度：平均 O(n)，最坏 O(n²)
• 空间复杂度：平均 O(log n)（递归栈），最坏 O(n)

三、堆（优先队列）方案

3.1 基本思路

维护一个大小为 K 的小顶堆（最小堆）。遍历数组：

• 堆不满时，直接入堆
• 堆满了且新元素 > 堆顶，弹出堆顶，新元素入堆
• 堆满了且新元素 <= 堆顶，跳过

遍历结束后，堆顶就是第 K 大的元素。

为什么用小顶堆而不是大顶堆？

因为我们维护的是”前 K 大”的集合，堆顶是这个集合中最小的元素。新元素如果比堆顶大，说明它应该进入”前 K 大”的集合，堆顶被淘汰。

3.2 JavaScript 中的堆实现

JavaScript 没有内置的优先队列，需要手写一个最小堆：

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return top;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;

      if (left < n && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < n && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }
      if (smallest === i) break;

      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

3.3 用堆解决第 K 大元素（LeetCode 215）

function findKthLargest(nums, k) {
  const heap = new MinHeap();

  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) {
      heap.pop(); // 弹出最小的，保持堆大小为 k
    }
  }

  return heap.peek(); // 堆顶就是第 k 大
}

复杂度分析：

• 时间复杂度：O(n log k)，每个元素最多做一次入堆和出堆操作，每次 O(log k)
• 空间复杂度：O(k)

四、三种方案的复杂度对比

选择策略：

• 面试中默认：先说排序法（保底），然后说快速选择（最优平均），再提堆方案（工程上更实用）
• k 很小时：堆方案优势明显，O(n log k) ≈ O(n)
• 数据是流式的（不断有新数据进来）：只能用堆，因为快速选择需要全部数据
• 需要修改原数组：快速选择会修改原数组（原地操作），如果不允许修改就用堆

五、经典题：前 K 个高频元素（LeetCode 347）

给定一个整数数组 nums 和一个整数 k，返回其中出现频率前 k 高的元素。

这道题是 TopK 的变体——不是找”值最大的 K 个”，而是找”频率最高的 K 个”。

5.1 哈希表 + 排序

function topKFrequent(nums, k) {
  // 统计频率
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  // 按频率排序
  return [...freqMap.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(entry => entry[0]);
}

时间复杂度 O(n log n)。

5.2 哈希表 + 小顶堆

function topKFrequent(nums, k) {
  // 统计频率
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  // 用大小为 k 的小顶堆维护前 k 高频元素
  // 这里简化实现，用数组模拟堆排序
  const entries = [...freqMap.entries()];

  // 使用小顶堆
  const heap = new MinHeapWithCompare((a, b) => a[1] - b[1]);

  for (const entry of entries) {
    heap.push(entry);
    if (heap.size() > k) {
      heap.pop();
    }
  }

  return heap.heap.map(entry => entry[0]);
}

时间复杂度 O(n log k)。

5.3 桶排序（最优解）

function topKFrequent(nums, k) {
  // 统计频率
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  // 桶排序：下标是频率，值是具有该频率的元素列表
  const buckets = new Array(nums.length + 1).fill(null).map(() => []);
  for (const [num, freq] of freqMap) {
    buckets[freq].push(num);
  }

  // 从高频到低频收集结果
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }

  return result.slice(0, k);
}

桶排序的思路：频率的范围是 [1, n]，我们创建 n + 1 个桶，第 i 个桶存放出现频率为 i 的元素。然后从后往前遍历桶，收集前 k 个元素。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

常见误区

误区一：“TopK 问题用排序就够了”

排序是最简单的方案，但时间复杂度是 O(n log n)，没有利用”只需要前 K 个”这个条件。面试中如果只给出排序解法，面试官一定会追问更优的方案。

误区二：“快速选择算法的时间复杂度一定是 O(n)”

快速选择的平均时间复杂度是 O(n)，但最坏情况是 O(n²)（每次 pivot 选到了极端值）。通过随机选取 pivot 可以让最坏情况出现的概率极低，但严格来说，只有使用”中位数的中位数”算法才能保证最坏 O(n)，不过那个算法实现起来非常复杂，面试中不需要掌握。

误区三：“堆的方案比快速选择差”

这两种方案各有优劣。快速选择平均更快（O(n) vs O(n log k)），但堆方案有两个独特优势：（1）适用于流式数据——新数据不断进来时，堆方案可以增量更新，快速选择必须重新计算；（2）不需要修改原数组——快速选择是原地操作，会改变数组元素的顺序。

误区四：“JavaScript 有内置的优先队列”

JavaScript 标准库里没有优先队列/堆的数据结构。面试中如果要用堆，需要自己手写。虽然代码量不少，但核心操作只有 bubbleUp（上浮）和 sinkDown（下沉），理解了原理就能快速写出来。

小结

TopK 问题是面试中最经典的选择问题，三种解法分别代表了不同的思路和权衡。

核心要点

1. 排序法：O(n log n)，最简单但做了多余的工作
2. 快速选择：平均 O(n)，基于 partition 只递归一侧，需要随机 pivot 避免最坏情况
3. 堆方案：O(n log k)，维护大小为 K 的小顶堆，适合流式数据和超大数据量
4. 选择策略：数据全在内存中用快速选择，流式数据或不能修改原数组用堆
5. 前 K 个高频元素：先统计频率，再用 TopK 找前 K 高频的。桶排序可以做到 O(n)

本章思维导图

练习挑战

第一题 ⭐：最大的第 K 个元素（直接排序）

给定数组 [3, 2, 3, 1, 2, 4, 5, 5, 6] 和 k = 4，找出第 4 大的元素。

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

// findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
// 排序后：[6, 5, 5, 4, 3, 3, 2, 2, 1]
// 第 4 大 = 4

第二题 ⭐⭐：手写最小堆解决第 K 大元素

用堆方案解决 LeetCode 215，要求完整手写 MinHeap。

class MinHeap {
  constructor() { this.heap = []; }

  size() { return this.heap.length; }
  peek() { return this.heap[0]; }

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

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      let i = 0;
      while (true) {
        let smallest = i;
        const l = 2 * i + 1, r = 2 * i + 2;
        if (l < this.heap.length && this.heap[l] < this.heap[smallest]) smallest = l;
        if (r < this.heap.length && this.heap[r] < this.heap[smallest]) smallest = r;
        if (smallest === i) break;
        [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

第三题 ⭐⭐⭐：数据流的中位数（LeetCode 295）

设计一个数据结构，支持以下操作：addNum(num) 添加一个数，findMedian() 返回当前所有数的中位数。

class MedianFinder {
  constructor() {
    this.maxHeap = new MaxHeap(); // 存较小的一半
    this.minHeap = new MinHeap(); // 存较大的一半
  }

  addNum(num) {
    // 先加到较小一半
    this.maxHeap.push(num);
    // 确保较小一半的最大值 <= 较大一半的最小值
    this.minHeap.push(this.maxHeap.pop());
    // 平衡两个堆的大小
    if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.push(this.minHeap.pop());
    }
  }

  findMedian() {
    if (this.maxHeap.size() > this.minHeap.size()) {
      return this.maxHeap.peek();
    }
    return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
  }
}

// MaxHeap 通过在 MinHeap 中取反实现
class MaxHeap extends MinHeap {
  push(val) { super.push(-val); }
  pop() { return -super.pop(); }
  peek() { return -super.peek(); }
}

自我检测

• 能说出 TopK 问题的三种解法及其时间复杂度
• 能手写快速选择算法，包括 partition 操作和随机 pivot
• 能解释快速选择为什么平均是 O(n)，以及最坏情况如何避免
• 能手写最小堆的 push 和 pop 操作
• 能用堆方案解决第 K 大元素问题
• 能根据场景选择合适的 TopK 方案（内存 vs 流式 vs 是否修改数组）
• 能解决”前 K 个高频元素”，并说出桶排序的 O(n) 思路
• 能在面试中从简单到最优逐步展示三种方案

下一站：项目经历篇。 算法篇到这里就结束了——双指针、滑动窗口、二分法、前缀和、单调栈、链表、二叉树、动态规划、TopK，这九个专题涵盖了前端面试中最高频的算法考点。但面试不只是做题，面试官更想知道”你做过什么、你是怎么做的”。接下来的项目经历篇，我们会从技术通识、技术深度、业务价值、团队协作、学习能力等多个维度，教你把项目经历讲出彩。