本文概览：本文讲解前 K 个高频元素的核心思路：先用哈希表统计频率，再用"按频率比较"的大小为 k 的最小堆求前 k 个，框架复用上一题，只换比较器

一、题目

image-20260906003000001

二、题目分析

1. 题目要求

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

例子：nums = [1, 1, 1, 2, 2, 3]，k = 2

1
2
3
4
元素:  1  2  3
频率:  3  2  1

前 2 个高频元素 → [1, 2]

和上一题的区别：上一题比的是元素值的大小，这题比的是出现频率的高低。元素本身多大无所谓，谁出现得多谁排前面。

2. 第一步：先统计频率（两种思路共同的前置步骤）

要比频率，先得知道每个元素的频率。原始数组是乱的，直接看不出来，所以第一步都是一样的：用哈希表统计每个元素的出现次数。

1
2
3
4
5
6
7
8
nums = [1, 1, 1, 2, 2, 3]

遍历统计：
1 → 出现 3 次
2 → 出现 2 次
3 → 出现 1 次

map = {1: 3, 2: 2, 3: 1}

统计完之后，问题就变成了：在 (元素, 频率) 条目里，找频率最高的前 k 个——这不就是上一题的 Top K 问题吗？

3. 方法一：按频率整体排序

最直觉的做法：把所有条目按频率降序排序，取前 k 个。

排序可以直接用 List.sort（内部就是归并一类的稳定排序），不需要手写归并或快排。

问题：和上一题一样，整体排序是 O(m log m)（m 为不同元素的个数），但我们只需要前 k 个，排后面的部分完全浪费了。

4. 方法二：大小为 k 的最小堆

框架和上一题完全一致，依旧是维护一个大小为 k 的最小堆，堆里始终保留"目前见过的频率前 k 高的元素"，堆顶就是门槛。

唯一要改的地方：堆的比较规则。上一题堆里存的是整数，默认按数值比；这题要按频率比——也就是说需要重写这个最小堆的排序器，可以用 lambda 简写：

1
PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(map::get));

最小堆的原理（物理数组 + 逻辑完全二叉树、上浮、下沉）在上一篇博客里已经详细讲解过，这里不再重复，不熟悉的可以先看：

三、思路概览

方法一：排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] topKFrequent(int[] nums, int k) {
    // 哈希表统计元素出现次数
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    // 所有条目按频率降序排序
    List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
    list.sort((a, b) -> b.getValue() - a.getValue());
    // 取前 k 个
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = list.get(i).getKey();
    }
    return res;
}

时间复杂度 O(m log m)，m 为不同元素个数。

方法二：大小为 k 的最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int[] topKFrequent(int[] nums, int k) {
    // 哈希表统计元素出现次数
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    // 堆排序（按频率比较的最小堆）
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(map::get));
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        // 堆没满 k 个，直接入堆
        if (minHeap.size() < k) {
            minHeap.offer(entry.getKey());
        } else {
            // 新条目的频率 > 堆顶元素的频率，替换
            if (entry.getValue() > map.get(minHeap.peek())) {
                minHeap.poll();
                minHeap.offer(entry.getKey());
            }
        }
    }
    // 从堆中获取前 k 个元素
    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        res[i] = minHeap.poll();
    }
    return res;
}

思路简要说明：

  1. 前置统计：HashMap 记录每个元素的出现次数
  2. 比较规则换成频率：Comparator.comparingInt(map::get)，堆内存元素值，但比较时通过 map 查频率
  3. 框架与上一题一致：堆没满直接入；满了之后，新条目频率 > 堆顶频率才替换
  4. 结果倒着填：poll 吐出的是按频率从小到大的顺序，从数组末位往前填，结果就是频率从高到低
  5. **时间复杂度 O(m log k)**：m 个条目，每个最多一次入堆/出堆，单次 O(log k)

四、思路详解

第一步：为什么第一步必须是哈希表统计？

频率信息在原始数组里是"隐藏"的。要比较两个元素谁的频率高，就得知道它们各出现了多少次；要知道出现了多少次，就得扫一遍数组数一数。

所以不管后面用排序还是用堆，第一步都是把频率数出来，存进哈希表：元素 → 频率。

这一步顺便完成了去重——数组里的重复元素在 map 里只剩一个条目，后面处理的就是 m 个不同元素的条目，而不是 n 个原始元素。

第二步：这题和上一题到底哪里一样、哪里不一样？

一样的（框架直接复用）：

  • 都是 Top K 问题：留前 k 个、踢掉其余
  • 都是大小为 k 的最小堆：堆顶是"门槛"
  • 替换逻辑一样：新条目 > 堆顶门槛 → 弹出堆顶、加入新条目

不一样的（比较规则）：

  • 上一题：比较的是元素值，堆内存的 Integer 本身就能比
  • 这题：比较的是频率，堆里存的元素值（比如 1 和 2）本身比大小没有意义，1 比 2 小，但 1 的频率比 2 高，要留下的是 1

所以关键动作就是重写比较器，把"比数值"换成"比 map 里查出来的频率"。

第三步：Comparator.comparingInt(map::get) 是怎么工作的？

PriorityQueue 构造时可以传入一个比较器，堆内部所有比较（上浮、下沉时的父子比较）都会用它。

拆开看这段代码：

1
Comparator.comparingInt(map::get)
  • map::get：方法引用，等价于 元素 -> map.get(元素)，即传入堆里的元素，查出它的频率
  • Comparator.comparingInt(...)：拿查出来的频率做 int 比较

效果：堆里存的还是元素值（Integer），但每次需要比较两个元素谁"更小"时，实际比的是它们的频率。频率小的在堆顶。

这样一来，上一题讲的上浮、下沉、索引公式全部原样生效，只是"大小"的定义换了。

第四步：替换条件的细节

1
2
3
4
if (entry.getValue() > map.get(minHeap.peek())) {
    minHeap.poll();
    minHeap.offer(entry.getKey());
}

两个容易看错的地方：

  1. 左边是 entry.getValue()：当前遍历条目的频率
  2. 右边是 map.get(minHeap.peek())：先 peek() 拿到堆顶的元素值，再拿这个元素值去 map 查频率

两边比的都是频率，不是元素值。这个写法比上一题多绕了一层（堆里是元素、比的是频率），读代码时要注意区分。

第五步：结果数组为什么倒着填？

1
2
3
4
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--) {
    res[i] = minHeap.poll();
}

poll 依次吐出的是按频率从小到大的顺序（每次吐当前最小）：

1
2
poll 顺序（频率从小到大）:  第1个     第2个   ...   第k个
填入位置:                  res[k-1]  res[k-2] ...  res[0]

从 res[k-1] 往 res[0] 倒着填，res[0] 最后填的是频率最高的，最终结果就是频率从高到低的顺序。

（题目其实不要求结果有序，但这样写顺便得到了有序结果，而且循环结构很自然。）

完整执行过程

以 nums = [1, 1, 1, 2, 2, 3]，k = 2 为例：

第一步：统计频率

1
2
3
4
元素:  1  2  3
频率:  3  2  1

map = {1: 3, 2: 2, 3: 1}

第二步：遍历条目维护堆（堆内括号标注频率）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
entry = 1（频率3）：size(0) < 2，直接入堆
  minHeap = [1(3)]

entry = 2（频率2）：size(1) < 2，直接入堆
  [1(3), 2(2)] → 按频率比：2 < 3 → 2 上浮到堆顶
  minHeap = [2(2), 1(3)]

        2(2)
       /
      1(3)

entry = 3（频率1）：size(2) 已满
  频率1 > 堆顶 2 的频率2？ 1 > 2 不成立 → 丢弃

**第三步：倒序填结果**

res[1] = poll() = 2（频率小，先出）
res[0] = poll() = 1（频率大，后出）

res = [1, 2] ✓

注意 entry = 3 这一步：如果按元素值比，3 > 2 会替换进去，答案就错了；按频率比，1 < 2 直接丢弃——这就是比较器改对了的价值。

复杂度分析

**时间复杂度 O(n + m log k)**：

  • 统计频率：O(n)，遍历数组一次
  • 维护堆：m 个条目，每个最多一次入堆 + 一次出堆，单次 O(log k)，共 O(m log k)
  • m ≤ n，当 k 远小于 m 时，比方法一的 O(m log m) 快

**空间复杂度 O(m + k)**：哈希表存 m 个条目，堆最多 k 个元素。

五、总结

前 K 个高频元素的核心思路：

  1. 前置统计：HashMap 数出每个元素的频率，同时完成去重
  2. 框架复用：和第 K 大元素完全一样的"大小为 k 的最小堆"框架
  3. 关键改动：比较器从"比数值"换成"比频率"——Comparator.comparingInt(map::get)
  4. 替换条件：两边都是频率（entry.getValue() vs map.get(peek())），别看错成元素值
  5. 结果倒填：poll 吐出频率从小到大，倒着填进数组得到频率从高到低

Top K 框架的复用心法：

  • 容器大小永远是 k，堆顶永远是门槛
  • 要留什么，就定义好"谁大谁小"——比数值、比频率、比长度，换个比较器，框架原样跑

这题也说明了比较器是最小堆的灵魂：堆只认比较器定义的"大小"，不管你存的是数字、元素还是对象。