LeetCode 347. 前 K 个高频元素

约 5 分钟
文章信息 20 个分类 8 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 百度 小红书 快手 滴滴 商汤 旷视
标签
数组 哈希表 排序 堆（优先队列） 分治 计数 快速选择 桶排序

题目描述

✅ 347. 前 K 个高频元素

image-20260928203044559

image-20260928203044560

题意分析

返回数组中出现次数最高的 k 个不同元素，比较依据是频次，不是元素本身的大小。题目保证 k 合法，且应选出的元素集合唯一，返回顺序可以任意。

同频元素仍可能有多个，“答案唯一”不表示所有元素的频次都不同。先统计每个值出现多少次，再挑出频次最大的 k 项即可；由于频次最多等于数组长度，可以利用这个有限范围避免对全部元素排序。

解法：哈希计数 + 频率桶

核心思路

[!blue]

先用哈希表 freq 记录“元素值 → 出现次数”。同一个值无论在数组中出现多少次，计数表中都只有一项，因此后续选择面向的是不同元素，不会把某个高频值重复放进答案。

设数组长度为 n，任意元素的频次都在 [1, n]。建立长度为 n + 1 的桶数组，让 buckets[c] 存放所有恰好出现 c 次的元素。桶下标对应频次，桶内保存元素值，因此负数或较大的元素值都不影响下标是否合法。

遍历计数表，把每个不同元素放入其频次对应的桶。同一频次可能对应多个元素，所以每个桶是一个列表；Java 在第一次遇到某个频次时创建这个列表，Go 则可以直接向空切片追加。

从下标 n 向 1 扫描桶，先输出高频桶，再输出低频桶。当前准备输出的元素，频次不会低于尚未扫描桶中的任何元素，因此依次收集的就是频次最高的一批。得到 k 个元素后立即停止，避免返回多余结果。

桶内元素的频次相同，而返回顺序不受限制，所以不需要再对桶内排序。每个不同元素只进入一个桶并最多输出一次，结合倒序扫描就能同时保证结果不重复、频次符合要求。

解题步骤

  1. 遍历原数组，用哈希表统计每个元素的频次。
  2. 创建 n + 1 个桶，保留下标 n，因为单个元素可能出现 n 次。
  3. 遍历计数表，将每个元素加入 buckets[对应频次]。
  4. 从频次 n 倒序扫描到 1，跳过空桶，将非空桶中的元素写入结果。
  5. 内外循环都在收满 k 个元素时停止，返回结果。

代码实现

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)$，哈希计数为线性时间，不同元素入桶最多 n 次，扫描桶下标最多 n 次，收集的元素也不超过 n 个。
  • 空间复杂度：$O(n)$，哈希表、桶数组以及所有桶内列表的元素总量均为线性规模，返回结果另外需要 $O(k)$ 空间。

关键点总结

[!green]

  • 桶的下标是频次而不是元素值；负数元素也能正常处理。
  • 频次值域 [1,n] 是线性解法的突破口，本质是用数组下标代替比较。
  • 返回顺序任意，同频桶内无需额外排序。

易错点总结

[!yellow]

  • 桶数组只开 n 个位置：频次可以等于 n，必须能访问下标 n，所以长度是 n + 1。
  • 把元素值当桶下标：桶按频次分组，元素本身可能为负，不能直接用作下标。
  • 每个桶只保存一个元素：不同元素可能同频，需要列表保存全部候选。
  • 遍历 Java 的空桶：没有初始化的桶为 null，读取前应跳过。
  • 只结束内层循环：收满 k 个后，外层也必须停止，否则会越界写入或返回过多元素。

相似题目

题目 难度 关联与区别
692. 前K个高频单词 中等 同样先统计频次再选前k，原题是单词且有字典序并列规则。
215. 数组中的第K个最大元素 中等 同样做TopK选择，但本题排名依据是出现频次而不是元素数值。
703. 数据流中的第 K 大元素 简单 用大小受限的堆保留排名靠前的候选；本题以元素频次为排序依据，该题支持持续插入时维护第 k 大。
973. 最接近原点的 K 个点 中等 用大小受限的堆保留排名靠前的候选；本题以元素频次为排序依据，该题以到原点的平方距离为排序依据。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/07679557
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！