347. 前K个高频元素#

今天我们来攻克一道非常实用的题目 - LeetCode 347「前K个高频元素」。这个问题不仅在面试中常见，在实际工作中也经常遇到。让我们一起探索几种解决方案！

📚 生活中的场景#

想象你是一个商场经理，想知道哪些商品最受欢迎。你手上有一串销售记录，需要找出销量前K名的商品。这就是我们今天要解决的问题的现实版本！

问题描述#

题目目标#

给定一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。答案可以按任意顺序返回。

示例 1#

输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 说明： 输出顺序不固定

💡 问题定义#

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

比如说：

输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
解释：1出现了3次，2出现了2次，3出现了1次，所以前两个高频元素是1和2

java

🤔 解决方案#

1. 小顶堆解法#

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // frequencyMap：键是数字，值是该数字在数组中的出现次数
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        // 遍历原数组，逐个累加频率
        for (int num : nums) {
            // getOrDefault(num, 0)：如果 num 还没出现过，默认频率按 0 处理
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 小顶堆：堆顶存放“当前堆内频率最小的元素”
        // 比较规则按频率升序，这样当堆超出 k 时可以快速淘汰最低频元素
        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a, b) -> frequencyMap.get(a) - frequencyMap.get(b)
        );

        // 遍历所有不同数字，维护“大小最多为 k 的小顶堆”
        for (int num : frequencyMap.keySet()) {
            // 先把当前数字放入堆
            heap.offer(num);
            // 若堆大小超过 k，弹出堆顶（当前最低频），保证只保留前 k 高频候选
            if (heap.size() > k) {
                heap.poll();
            }
        }

        // 结果数组长度为 k，用于存储前 k 高频元素
        int[] result = new int[k];
        // 从后往前填充：因为小顶堆每次弹出的是“较低频”，倒着填能更直观地保留高频在前
        for (int i = k - 1; i >= 0; i--) {
            // 依次弹出堆中元素写入结果
            result[i] = heap.poll();
        }

        // 返回前 k 个高频元素（顺序不要求固定）
        return result;
    }
}

java

2. 桶排序解法（最优解）#

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 第一步：统计每个数字出现频率
        // frequencyMap：key=数字，value=出现次数
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        // 遍历数组并累加频率
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 第二步：创建桶数组
        // 下标 i 表示“频率为 i”，buckets[i] 存放所有出现 i 次的数字
        // 频率最大不会超过 nums.length，所以桶大小为 nums.length + 1
        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        // 初始化每个桶，避免后续 add 时空指针
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 第三步：把每个数字放入“对应频率”的桶中
        for (int num : frequencyMap.keySet()) {
            // 读取该数字的出现次数（即桶下标）
            int frequency = frequencyMap.get(num);
            // 放入该频率对应的桶里
            buckets[frequency].add(num);
        }

        // 第四步：从高频到低频收集元素，直到凑够 k 个
        // result 临时保存收集到的数字
        List<Integer> result = new ArrayList<>();
        // 从最大频率开始向下扫描桶
        for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
            // 当前频率桶内可能有多个数字，全部加入候选结果
            result.addAll(buckets[i]);
        }

        // 第五步：把 List<Integer> 转成 int[]
        // 由于最后一个桶可能一次加入超过 k 个，使用 limit(k) 截断到恰好 k 个
        return result.stream().mapToInt(i -> i).limit(k).toArray();
    }
}

java

📝 方法比较#

小顶堆法
- 时间复杂度：O(nlogk)
- 空间复杂度：O(n)
- 优点：适合处理动态数据
- 缺点：需要额外的堆空间
桶排序法
- 时间复杂度：O(n)
- 空间复杂度：O(n)
- 优点：最优的时间复杂度
- 缺点：需要额外的桶空间

💡 算法思路解析#

小顶堆法的思路：#

先用哈希表统计每个元素的频率
维护一个大小为k的小顶堆
遍历频率表，更新堆
最后堆中剩下的就是前k个高频元素

桶排序法的思路：#

同样先统计频率
创建n+1个桶（频率范围是0到n）
根据频率把元素放入对应的桶
从后往前收集k个元素

🎯 易错点提醒#

频率统计
- 别忘了先统计频率
- 使用HashMap的getOrDefault方法更简洁
堆的比较器
- 小顶堆要按频率比较，不是数字本身
- lambda表达式注意参数顺序
结果收集
- 注意收集够k个元素就停止
- 桶可能为空，要跳过

🎨 数据结构图解#

graph TB
    A[输入数组] --> B[频率统计]
    B --> C{选择方法}
    C -->|方法1| D[小顶堆]
    C -->|方法2| E[桶排序]
    D --> F[结果数组]
    E --> F

🌟 面试技巧#

先说思路
- “我们首先需要统计每个元素的频率”
- “然后可以用小顶堆或桶排序来找出前k个”
比较方法
- 分析各种方法的优缺点
- 说明在不同场景下的选择
补充优化
- 提到空间优化的可能性
- 讨论处理动态数据的方案

🎩 延伸应用#

这个问题在实际工作中有很多应用：

热门商品分析
- 找出销量最高的商品
- 实时监控热销商品
网站访问统计
- 统计最常访问的页面
- 分析用户行为模式
系统监控
- 发现最频繁的错误类型
- 优化系统性能瓶颈

这道题告诉我们：有时候换个思路，用不同的数据结构，可以得到更优的解法。如果你对这个话题还有任何疑问，欢迎在评论区讨论！