刷题笔记：LeetCode 347. 前 K 个高频元素

灵茶山艾府题解，灵神神了

核心：桶的下标天然代表了“出现次数（频次）”

这个解法之所以倒序遍历顺序完全正确，是因为代码在第二步建立桶时做了一个极其巧妙的映射：

$\text{桶的下标 } i = \text{元素出现的次数（频次）}$

---

1. 题目

• 目标：给定整数数组 nums 和整数 k，返回出现频率前 k 高的元素。
• 通用第一步：无论哪种解法，必须先用 HashMap 统计每个元素的出现频次（$O(N)$）。

---

2. 三种解法对比与权衡

解法	时间复杂度	空间复杂度	核心逻辑	适用场景
全排序（暴力直觉）	$O(M \log M)$	$O(M)$	把不重复的元素提取到 List，直接按频次从大到小调用 sort，切前 $k$ 个。	代码极短。
小顶堆	$O(M \log K)$	$O(K)$	维护容量为 $k$ 的优先队列（按频次升序）。超过 $k$ 个就踢出堆顶（淘汰低频）。	标准解。适合无界数据流（Stream）、内存受限场景。
桶排序（线性最优）	$O(N)$	$O(N)$	以“频次”作为桶下标（$1 \sim N$），将元素扔进对应频次的桶，从最大频次倒序收集满 $k$ 个返回。	理论最优解。利用频次天然有界（$1 \le freq \le N$）消除比较开销。

注：$N$ 为数组总长度，$M$ 为不同元素个数（$M \le N$）。

---

3. 最优解实现精要（桶排序 $O(N)$）

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 第一步：用 HashMap 统计每个数字出现的频次
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 第二步：创建桶。频次最多为 nums.length，所以创建 nums.length + 1 个空桶
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            buckets.add(new ArrayList<>());
        }

        // 把数字按照“出现次数”作为下标放进对应的桶里
        for (int num : countMap.keySet()) {
            int freq = countMap.get(num);
            buckets.get(freq).add(num);
        }

        // 第三步：从最高频次倒序往回找，凑齐 k 个数字立即返回
        int[] result = new int[k];
        int index = 0;

        for (int i = buckets.size() - 1; i >= 0 && index < k; i--) {
            for (int num : buckets.get(i)) {
                result[index++] = num;
                // 已经收集满 k 个就提前结束
                if (index == k) {
                    break;
                }
            }
        }

        return result;
    }
}

---