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

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

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

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

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

---

1. 核心题意与拆解

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

---

2. 三种解法对比与权衡

解法	时间复杂度	空间复杂度	核心逻辑	适用场景
全排序（暴力直觉）	$O(M \log M)$	$O(M)$	把不重复的元素提取到 List，直接按频次从大到小调用 sort，切前 $k$ 个。	刷题快速 AC，代码极短。
小顶堆（工业标准）	$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)$）

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计频次
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int maxCnt = Collections.max(cnt.values());

        // 2. 建立频次桶：桶下标 i = 出现频次
        List<Integer>[] buckets = new ArrayList[maxCnt + 1];
        Arrays.setAll(buckets, _ -> new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            buckets[e.getValue()].add(e.getKey());
        }

        // 3. 倒序扫桶（从高频到低频天然有序），收集满 k 个即停
        int[] ans = new int[k];
        int j = 0;
        for (int i = maxCnt; j < k; i--) {
            for (int x : buckets[i]) {
                ans[j++] = x;
            }
        }
        return ans;
    }
}

---