LeetCode 347. 前 K 个高频元素

2026-09-02 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 中等已解决 20-50 字节跳动微软美团阿里巴巴快手腾讯百度滴滴京东华为拼多多商汤旷视小红书 LeetCode 热题 100

题目描述

✅ 347. 前 K 个高频元素

题意分析

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

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

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

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

解法：哈希计数 + 频率桶

核心思路

问题关键：先用哈希表得到“元素 → 频次”，再从不同元素中取频次最高的 k 个。若将 m 个不同元素全部排序，需要 $O(m \log m)$；但频次只可能落在 [1,n]，没必要建立完整次序。

为什么选频率桶：建立 buckets[c]，专门存放出现 c 次的元素。频次值域最多只有 n + 1 个位置，因此可以用数组下标完成分组，再从高频桶向低频桶收集答案，把比较排序降为线性扫描。最小堆也能做到 $O(n+m\log k)$，但本题有限的频次值域让桶更直接、复杂度更优。

不变量：buckets[c] 中的每个元素都恰好出现 c 次；倒序扫描到频次 c 时，所有频次大于 c 的元素都已被收集，频次小于 c 的元素都还未访问。

正确性：倒序访问桶时，取出顺序按频次单调不增。因此前 k 个被取出的元素，其频次不会小于任何尚未取出的元素，正好构成前 k 高频元素；题目保证答案唯一，所以无需处理第 k 名处的平局规则。

解题步骤

遍历 nums，用哈希表统计每个元素的出现次数。

创建长度为 n + 1 的桶数组；最大频次可能是 n，所以必须保留下标 n。

遍历计数表，将元素放入 buckets[frequency]。同频元素可能有多个，因此每个桶是列表。

从频次 n 向 1 倒序扫描，将非空桶中的元素加入结果，收满 k 个立即结束。

口述样例：[1,1,1,2,2,3], k=2 的计数是 {1:3, 2:2, 3:1}，对应 bucket[3]=[1]、bucket[2]=[2]、bucket[1]=[3]；倒序先取 1，再取 2，得到 [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)$，其中不同元素数 $m\le n$。

空间复杂度：$O(n)$。哈希表、桶数组及桶内元素总量都不超过线性规模；不计返回结果仍为 $O(n)$。

关键点总结

桶的下标是频次而不是元素值；负数元素也能正常处理。

频次值域 [1,n] 是线性解法的突破口，本质是用数组下标代替比较。

若频次值域很大或无法开桶，可改用大小为 k 的最小堆，时间 $O(n+m\log k)$、空间 $O(m+k)$。

返回顺序任意；若题目增加同频排序规则，桶内还需按规则处理。

易错点总结

桶长度少一位：[7,7,7], k=1 的频次为 3，桶必须开成 n+1 才能访问下标 n。

未跳过 Java 的空桶：未初始化的 buckets[count] 是 null，直接遍历会触发空指针。

把元素值当桶下标：[-1,-1,3] 会访问负下标；桶索引必须是频次。

收满 k 个后仍继续写结果：外层循环也要受 idx < k 限制，避免越界或返回多余元素。

相似题目

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