LeetCode LCR 060. 前 K 个高频元素

2026-03-28 HGNULB 约 10 分钟

文章信息 5 个分类 9 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 060. 前 K 个高频元素

题意分析

输入一个整数数组 nums 和一个整数 k，要求返回其中出现次数最多的 k 个元素，返回的顺序不作要求。

题目明确保证「答案唯一」，也就是不存在第 k 名与第 k+1 名出现次数相同的歧义情形，因此不需要额外设计打破平局的规则；同时 k 的取值保证合法，一定落在 1 到数组中不同元素个数之间，不必防御 k 越界或结果凑不满的情况。

有两个约束信号值得留意。其一，数组长度可以达到 $10^5$ 量级，而题目在进阶要求里直接写明「时间复杂度必须优于 $O(n \log n)$」，等于提前否决了「统计完再整体定序」这条路。其二，任何一个元素的出现次数最少是 1 次、最多是 n 次，这个统计量被牢牢卡在一段很窄的整数区间里，是个很强的暗示。

边界方面：数组只有一个元素时 k 只能是 1，直接返回该元素；所有元素互不相同时每个次数都是 1，此时任取 k 个都是合法答案；元素允许为负数，所以不能拿数值本身去当数组下标。

解法：哈希计数 + 频率桶

核心思路

最直接的做法是先用哈希表数出每个数字的出现次数，得到 m 个不同元素，再把它们按次数从大到小整体排序，取前 k 个。结果一定正确，但排序为全部 m 个元素确定了完整的先后次序，代价是 $O(m \log m)$。而题目只关心「谁进了前 k 名」，第 k+1 名之后彼此谁高谁低完全没人过问，这些多做的定序工作就是瓶颈所在，也正是进阶要求要砍掉的部分。

第一层观察是：既然只要前 k 名，就没必要把 m 个候选全留在手上，随时只保留「当前最强的 k 个」即可。承载这个想法的结构是一个大小恒为 k 的最小堆，堆内按出现次数比较。这里的对应关系最容易记反，务必咬死一句话：求前 k 大要用最小堆。因为最小堆的堆顶是候选集中次数最小的那个，也就是「下一个该被淘汰的人」，把淘汰对象放在 $O(1)$ 就能看到的位置，才是这个结构的价值。于是每处理一个新元素：堆没满就直接压入；堆已满时拿它的次数和堆顶比，大于堆顶就弹掉堆顶再压入，否则说明它连当前最弱的候选都比不过，直接丢弃。整个过程维持的不变量是：处理完前 i 个不同元素后，堆中恰好装着这 i 个元素里次数最大的 $\min(i, k)$ 个。堆的规模始终不超过 k，单次调整只要 $O(\log k)$，总代价 $O(m \log k)$，已经优于 $O(n \log n)$。

第二层观察进一步利用题意分析里那个「次数被卡在 1 到 n 之间」的信号：既然次数本身就是一个不大的正整数，它就可以直接充当数组下标，那么连比较和堆调整都可以省掉。开一个长度为 n + 1 的桶数组 buckets，把出现次数为 c 的所有数字挂进 buckets[c]，一次线性扫描就完成了「按次数分组」。此时维持的不变量是：buckets[c] 里的每个数字出现次数都恰好等于 c，且下标越大代表次数越高。于是从最大下标向下遍历，先被遇到的元素次数必然不低于后被遇到的，凑满 k 个立刻收工，整体降到 $O(n)$。桶的思想本质上是用「值域有限」换掉了「比较排序」，这也是本题最终解法采用的写法。

解题步骤

遍历数组，用哈希表 freq 把每个数字的出现次数累加出来。为什么先做这一步：题目问的是「次数」而不是「数值」，必须先把原始数组压缩成「数字 → 次数」的映射，后面所有比较才有依据。

开一个长度为 nums.length + 1 的桶数组 buckets，下标表示出现次数。为什么长度是 n + 1：出现次数最大就是 n（整个数组都是同一个数字），下标要能取到 n，所以数组长度得是 n + 1，下标 0 空着不用。

遍历 freq 的每个键值对，把数字挂到 buckets[count] 这一格里。为什么用「挂链」而不是直接赋值：不同数字完全可能次数相同（如都出现 2 次），一格里必须能装下多个数字，所以每格是一个列表。

从最大下标向下遍历桶，遇到空桶直接跳过。为什么从大到小：这正是「下标越大次数越高」这条不变量的兑现方式，倒着走就等价于按次数降序访问，而这个降序是分组时白送的，不花任何比较代价。

把桶内的数字依次写进结果数组，一旦写满 k 个就立即停止外层与内层循环。为什么可以立刻停：此时已收集的 k 个元素次数都不低于尚未访问的任何桶，加上题目保证答案唯一，它们就是标准答案，继续扫描纯属浪费。

以 [1,1,1,2,2,3], k = 2 走一遍：先统计得到计数表「1 → 3 次，2 → 2 次，3 → 1 次」。若按最小堆的思路推演：压入 (数字 1, 次数 3)，堆为 [(1,3)]；压入 (数字 2, 次数 2)，堆为 [(2,2), (1,3)]，堆顶是次数最小的 (2,2)；再来 (数字 3, 次数 1)，堆已满且 1 小于堆顶的 2，直接丢弃，堆保持 {1, 2}。若按本文的桶做法：n = 6，buckets[3] = [1]，buckets[2] = [2]，buckets[1] = [3]，其余为空；从下标 6 往下扫，6、5、4 全空跳过，下标 3 取出数字 1（已收 1 个），下标 2 取出数字 2（已收 2 个，等于 k）立即返回。两条路线的答案一致，结果为 [1, 2]。

代码实现

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            int count = entry.getValue();
            if (buckets[count] == null) {
                buckets[count] = new ArrayList<>();
            }
            buckets[count].add(entry.getKey());
        }

        int[] res = new int[k];
        int idx = 0;
        for (int count = buckets.length - 1; count >= 1 && idx < k; count--) {
            if (buckets[count] == null) {
                continue;
            }
            // 从高频桶向低频桶收集，先拿到的就是高频元素。
            for (int num : buckets[count]) {
                res[idx++] = num;
                if (idx == k) {
                    break;
                }
            }
        }
        return res;
    }
}

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }

    buckets := make([][]int, len(nums)+1)
    for num, count := range freq {
        buckets[count] = append(buckets[count], num)
    }

    res := make([]int, 0, k)
    for count := len(buckets) - 1; count >= 1 && len(res) < k; count-- {
        // 高频桶优先输出，桶内顺序不影响题意。
        for _, num := range buckets[count] {
            res = append(res, num)
            if len(res) == k {
                break
            }
        }
    }
    return res
}

复杂度分析

时间复杂度：$O(n)$。凭什么是线性：统计次数扫描数组一次是 $O(n)$；遍历哈希表入桶，不同元素个数 m 不超过 n，是 $O(m)$；倒序扫描桶时，桶数组共 n + 1 格、所有桶内元素总数也是 m，因此扫描代价被 $O(n + m)$ 卡住。全程没有任何一次元素间的比较排序，所以不会退化出 $\log$ 因子。

空间复杂度：$O(n)$。凭什么：哈希表最多存 m 个键值对，桶数组固定 n + 1 格且所有桶内元素合计 m 个，两者都被 $O(n)$ 覆盖；输出数组占 $O(k)$，而 $k \le m \le n$。

关键点总结

只要「前 k 名」而不要全序，就不该做全排序。整体排序是在为不关心的名次买单，凡是题面出现「前 k 个」「第 k 大」，第一反应就该是能否只维护 k 个候选。

求前 k 大用最小堆，求前 k 小用最大堆，方向是反的。判断依据不是「要什么」，而是「堆顶要放谁」，堆顶必须是最容易被淘汰的那个，这样一次比较就能决定新元素的去留。

面试视角：本题写完 $O(n \log k)$ 的堆解法后，面试官几乎必然追问「能否做到 $O(n)$」。答案就是桶排序或计数排序思路，突破口在于「出现次数是 1 到 n 的整数」这个有限值域，把比较换成下标寻址。能主动说出这一层，才算真正答完 347。

值域有限是可以直接用下标索引取代比较的强信号。同类可迁移场景包括年龄、分数、字符集大小固定的字符计数等，这也是计数排序、基数排序共享的底层观察。

「答案唯一」这类保证要读出来并用上，它免除了平局裁决逻辑；一旦题目改成允许并列（例如 692 题要求次数相同时按字典序），桶内顺序就不再随意，解法必须相应加码。

易错点总结

错误写法：把全部不同元素塞进一个大小为 m 的最大堆，再连弹 k 次取答案。用例 [1,1,1,2,2,3], k = 2 → 结果虽然对，但建堆是 $O(m)$、每次弹出 $O(\log m)$，当 k 接近 m 时退化成 $O(m \log m)$，与进阶要求背道而驰；更糟的变体是「用最大堆但只留 k 个元素」，为了淘汰最小者不得不每轮把堆顶的最大值取走再放回，相当于要弹 n-k 次才能定位到该淘汰的人，纯属把最小堆的活硬塞给最大堆。正解是大小为 k 的最小堆，堆顶天然就是淘汰对象。

错误写法：桶数组开成 new ArrayList[nums.length]。用例 [7,7,7], k = 1 → 唯一元素出现 3 次，而 n = 3 时最大合法下标只有 2，写 buckets[3] 直接抛出下标越界，桶长度必须是 n + 1。

错误写法：忘记桶数组里存在大量空格子，直接 for (int num : buckets[count]) 遍历。用例 [1,1,1,2,2,3], k = 2 → 下标 6、5、4 对应的桶从未初始化，Java 里是 null，遍历时抛空指针，必须先判空跳过（Go 中空切片可安全遍历，但空判同样让意图更清晰）。

错误写法：内层循环写满 k 个后只 break 内层，外层继续往下扫。用例 [1,1,2,2,3,3], k = 2 → 结果数组下标继续自增，res[idx++] 越界；即便用列表接收也会多收元素返回错误长度。外层循环条件必须同时带上 idx < k。

错误写法：拿数字本身当桶下标，以为「值域也不大」。用例 [-1,-1,3] → 负数下标直接越界。桶的下标必须是出现次数，而不是元素值，这两者在本题里是完全不同的量。

错误写法：担心返回顺序不对而额外把结果排序。用例 [1,1,1,2,2,3], k = 2 → 返回 [2,1] 和 [1,2] 都判对，题目明确「按任意顺序返回」，多加一次排序既无必要又重新引入了 $\log$ 因子。

错误写法：在只出现一次的元素上做特判提前返回。用例 [1,2,3,4], k = 3 → 所有元素次数都是 1，全部堆在 buckets[1] 里，此时仍需正常从该桶取 3 个；误以为「没有高频元素就无解」会直接返回空数组。

错误写法：用 freq.get(num) + 1 累加计数。用例 [5] → 首次遇到 5 时哈希表中无此键，get 返回 null，自动拆箱触发空指针，应使用 getOrDefault(num, 0) + 1（Go 的 map 零值为 0，可直接 freq[num]++）。

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	只定位第 k 名这一个位置，比的是数值本身，可用快速选择
692. 前K个高频单词	中等	同样按次数取前 k，但答案不唯一，并列时须按字典序裁决
973. 最接近原点的 K 个点	中等	排序键换成到原点距离，值域连续因而无法用桶，只能靠堆
LCR 076. 数组中的第 K 个最大元素	中等	215 的同题，练原地划分与递归只走一侧的剪枝
剑指 Offer 40. 最小的k个数	简单	方向相反，求最小 k 个要改用大小为 k 的最大堆
面试题 17.14. 最小K个数	中等	同为求最小 k 个且顺序不限，可对比堆与快速选择的常数差异