LeetCode LCR 060. 前 K 个高频元素

约 5 分钟
文章信息 5 个分类 9 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 哈希表 排序 LCR 堆（优先队列） 分治 计数 快速选择 桶排序

题目描述

✅ LCR 060. 前 K 个高频元素

image-20260929010334522

题意分析

返回出现次数最多的 k 个不同元素，结果顺序不限。排名依据是出现次数，不是元素数值；题目保证 k 合法且答案集合唯一。

进阶要求时间复杂度优于 O(n log n)。一次统计后，任何元素的频次都在 1...n 之间，可以直接按频次放入桶，不必对所有元素进行比较排序。

解法：哈希计数 + 频率桶

核心思路

[!blue]

先用哈希表 freq 统计“元素值 → 出现次数”。同一个数字只保留一条计数记录，之后从这张表挑选高频元素。

建立长度为 n+1 的数组 buckets，让 buckets[c] 保存所有出现 c 次的不同元素。下标代表次数，桶内保存元素值；不同元素可能同频，因此一个桶需要容纳多个值。元素为负也没有影响，因为负数作为哈希键和桶内数据，不作为桶下标。

从下标 n 向 1 扫描桶，就等于按频次从高到低访问元素。当前桶中的频次不低于之后任何桶，依次收集，取得 k 个时就得到了前 k 高频元素。

每个不同元素只进入一个桶，且只进入一次，不会重复输出。桶内顺序无需额外排序：返回顺序本来不限，题目又保证前 k 个元素的集合唯一，不需要设计同频时的取舍规则。

解题步骤

  1. 遍历原数组，统计每种元素的频次。
  2. 建立 n+1 个频率位置，将每个不同元素加入它对应的频次桶。
  3. 从高频向低频扫描，跳过空桶，依次把桶内元素加入结果。
  4. 收集到 k 个后结束。Java 内层填满后跳出，外层条件也检查数量；Go 同样在两层遍历中限制结果长度。

代码实现

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
}

复杂度分析

设数组长度为 n，不同元素数量为 m，且 m <= n。

  • 时间复杂度：期望 $O(n)$。哈希计数为期望 $O(n)$，入桶为 $O(m)$；扫描桶下标最多 n 次，所有桶内元素合计只有 m 个，合起来仍为线性时间。
  • 空间复杂度：$O(n)$，哈希表和桶内元素共为 $O(m)$，桶数组为 $O(n)$，结果为 $O(k)$。

关键点总结

[!green]

  • 频次被数组长度限制在有限整数范围内，可以用桶下标代替比较排序。
  • 桶下标是频次，桶内是元素；每个不同元素只入桶一次。
  • 倒序扫描天然按频次降序输出，取得 k 项即可停止。

易错点总结

[!yellow]

  • 按元素值大小选前 k 个：本题比较的是频次，数值较大不代表更高频。
  • 只开 n 个桶位置：频次最大可能是 n，需要长度 n+1 才能访问下标 n。
  • 每个频次只保存一个元素：同频元素会互相覆盖，应使用列表形式的桶。
  • 从低频向高频扫描：会先选到出现次数最少的元素。
  • 只跳出内层却让外层继续填充：结果可能超过 k 项，外层也要检查是否已收集完成。
  • 认为大小为 k 的堆总能严格优于全排序：当 k 与 n 同阶时仍可能是 O(n log n)，本实现用线性频率桶满足进阶要求。

相似题目

题目 难度 关联与区别
692. 前K个高频单词 中等 同样先统计频次再选前k，原题是单词且有字典序并列规则。
215. 数组中的第K个最大元素 中等 同样做TopK选择，但本题排名依据是出现频次而不是元素数值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/71560461
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！