前 K 个高频元素

题目描述
给定一个整数数组 nums 和一个整数 k，请返回数组中出现频率前 k 高的元素。可以按任意顺序返回答案。
示例：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
解释：元素 1 出现 3 次，元素 2 出现 2 次，元素 3 出现 1 次，所以频率前 2 高的元素是 1 和 2。

解题过程循序渐进讲解

步骤 1：统计每个元素的出现频率
首先，我们需要知道每个数字在数组中出现了多少次。这里很自然想到使用哈希表（在 Python 中可以用字典，C++ 中可以用 unordered_map，Java 中可以用 HashMap）来记录数字到出现次数的映射。

• 遍历数组 nums，对每个数字 num：
  • 如果 num 不在哈希表中，则插入并设置计数为 1。
  • 如果已在哈希表中，则将其计数加 1。
    这一步结束后，我们就得到了一个频率字典，例如 {1:3, 2:2, 3:1}。

步骤 2：将频率字典转换为可排序的结构
我们需要根据频率（即哈希表的值）来找出前 k 高的元素。一个直接的想法是：

• 将哈希表的键值对（数字，频率）放到一个列表里。
• 根据频率对列表进行排序，从高到低。
• 取前 k 个元素对应的数字。

这种方法的时间复杂度是 O(n log n)，其中 n 是不同数字的个数（最坏情况下 n 等于数组长度）。在大部分情况下可以接受，但我们可以用更优的方法做到平均 O(n)。

步骤 3：使用桶排序思想优化
因为频率最高不会超过数组长度 n，我们可以用“桶排序”的思想：

1. 创建长度为 n+1 的列表（桶）buckets，下标表示频率，每个桶是一个列表，存放该频率的所有数字。
2. 遍历步骤 1 得到的频率字典，将数字放入对应的频率桶中。
   例如：频率 3 的桶放入 [1]，频率 2 的桶放入 [2]，频率 1 的桶放入 [3]。
3. 从频率最高的桶（下标从 n 开始）向低频率遍历，收集数字，直到收集到 k 个数字为止。

这种方法时间复杂度是 O(n)，空间复杂度 O(n)。

步骤 4：使用最小堆（优先队列）的另一种方法
另一种常见且高效的方法是使用最小堆（min-heap）来维护频率最高的 k 个元素：

1. 首先同样用哈希表统计频率。
2. 遍历频率字典的每个键值对 (num, freq)：
   • 将 (freq, num) 放入最小堆（堆的大小限制为 k）。
   • 如果堆大小超过 k，则弹出堆顶（频率最小的元素）。
3. 遍历结束后，堆中剩下的就是频率最高的 k 个元素（不一定按频率排序，但题目不要求顺序）。
   这种方法时间复杂度 O(n log k)，当 k 远小于 n 时比全局排序更高效。

步骤 5：实现（以 Python 为例，采用桶排序方法）

def topKFrequent(nums, k):
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    # 桶排序
    n = len(nums)
    buckets = [[] for _ in range(n + 1)]
    for num, freq in freq_map.items():
        buckets[freq].append(num)
    
    result = []
    for i in range(n, 0, -1):
        if buckets[i]:
            result.extend(buckets[i])
        if len(result) >= k:
            break
    
    return result[:k]

步骤 6：复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。统计频率 O(n)，桶排序 O(n)，收集结果 O(n)。
• 空间复杂度：O(n)，用于哈希表和桶的存储。

小结
这个题目展示了哈希表用于频率统计，并结合桶排序（或堆）来高效获取前 k 个最高频元素。关键在于频率范围有限时，桶排序可达到线性时间复杂度，比直接排序更优。