347. 前 K 个高频元素

题目链接：347. 前 K 个高频元素

题目描述

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

核心思考：桶排序（Bucket Sort）加速

常规思路是统计频率后进行排序（$O(N \log N)$）或者使用堆（$O(N \log k)$）。但在本题中，频率的最大值不会超过数组的长度 $N$。利用这一特性，我们可以使用桶排序在 $O(N)$ 时间内解决。

1. 统计频率：首先使用哈希表（Python 中的 Counter）记录每个数字出现的次数。同时找出出现的最高频率 max_count。
2. 建立桶：创建一个长度为 max_count + 1 的列表 b，每个位置 b[i] 也是一个列表。
   • b[i] 的含义是：所有出现次数刚好为 i 次的数字集合。
3. 分配入桶：遍历哈希表，根据频率将对应的数字放入对应的桶中。
4. 逆序提取：从频率最高的桶（b[max_count]）开始向低频方向遍历。依次提取桶中的数字加入结果集，直到结果集的长度达到 k。

这种方法巧妙地利用了“频率是有界的”这一物理现实，避开了基于比较的排序，从而实现了线性时间复杂度。

解题思路 (Python)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        # 1. 统计频率
        count = Counter(nums)
        # 获取最大频率，作为桶数组的长度上限
        max_count = max(count.values())

        # 2. 建立桶：下标代表频率，内容代表该频率对应的数字列表
        b = [[] for _ in range(max_count + 1)]

        for key, value in count.items():
            b[value].append(key)
        
        # 3. 逆序从频率高的桶中提取前 k 个元素
        ans = []
        for e in reversed(b):
            ans += e
            if len(ans) >= k:
                # 注意：由于我们要的是前 k 个，如果该频率桶中的数字加完后正好或超过 k，截取返回即可
                return ans[:k]

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。频率统计需 $O(N)$，入桶需 $O(N)$，逆序扫描桶数组总共处理的元素个数也不会超过 $N$。
• 空间复杂度：$O(N)$。主要开销为存储频率的哈希表和用于桶排序的嵌套数组。
  说明：为了严谨，代码增加了一个对 ans 的截取处理 [:k] 以应对同一个频率桶包含多个元素导致 ans 长度超过 k 的边界情况。