我来给你讲解 LeetCode 第 347 题「前 K 个高频元素」。

1. 题目描述

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

示例 1：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2：

输入: nums = [1], k = 1
输出: [1]

要求：时间复杂度必须优于 O(n log n)，其中 n 是数组大小。

2. 问题分析

我们要找出出现次数最多的 k 个元素。
一个直观的思路是：

1. 统计每个元素出现的次数。
2. 根据次数排序，取前 k 个。

但排序的时间复杂度是 O(n log n)，虽然可以满足一般情况，但题目要求优于 O(n log n)，所以我们需要更优的解法。

3. 思路与步骤

3.1 统计频率

使用哈希表（字典）来统计每个数字出现的次数。
这一步时间复杂度 O(n)，空间复杂度 O(n)。

例如 nums = [1,1,1,2,2,3]，得到哈希表：

{1: 3, 2: 2, 3: 1}

3.2 如何取前 k 个高频元素

如果对所有元素按频率排序，是 O(m log m)，m 是不同数字的个数，最坏 m = n，则 O(n log n)，不符合要求。

我们可以用 最小堆（Min-Heap） 来优化：

• 维护一个大小为 k 的最小堆（按频率排序）。
• 遍历哈希表的每个元素：
  • 如果堆大小小于 k，直接加入堆。
  • 否则，比较当前元素的频率与堆顶（堆中最小频率）：
    • 如果当前频率大于堆顶频率，弹出堆顶，插入当前元素。
    • 否则跳过。
• 最后堆中剩下的就是频率最大的 k 个元素。

为什么用最小堆？
因为堆顶是堆中最小的频率，我们只保留比它大的，这样堆里始终是当前看到的最大的 k 个频率。

3.3 复杂度分析

• 建堆（大小为 k）的插入和删除是 O(log k)。
• 最坏情况下，m 个不同元素都要进堆一次，复杂度 O(m log k)。
• 由于 k ≤ m ≤ n，所以 O(m log k) 优于 O(n log n)。

4. 详细步骤示例

以 nums = [1,1,1,2,2,3], k = 2 为例：

1. 统计频率：

   1: 3
   2: 2
   3: 1
   

2. 用最小堆（存储 (频率, 元素)，按频率排序）：

   • 插入 (3, 1)，堆：[(3, 1)]，大小=1 < 2，继续。
   • 插入 (2, 2)，堆：[(2, 2), (3, 1)] 调整后堆顶是 (2, 2)？不对，最小堆堆顶是最小频率，所以应该是 (2, 2) 在堆顶？我们检查一下：
     实际上插入过程：
     插入 (3,1) → 堆 [(3,1)]
     插入 (2,2) → 堆调整为 [(2,2), (3,1)]，堆顶是 (2,2)。
   • 插入 (1, 3)：
     当前堆顶频率=2，新元素频率=1 < 2，不加入（因为我们要保留大的，堆大小已到 k，小的不要）。

3. 最后堆中元素：[(2,2), (3,1)]，对应的数字是 [2, 1]（顺序任意）。

输出 [1, 2]。

5. 实现细节（Python示例）

import heapq
from collections import Counter

def topKFrequent(nums, k):
    # 统计频率
    count = Counter(nums)
    
    # 建立最小堆
    heap = []
    for num, freq in count.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, num))
        else:
            if freq > heap[0][0]:
                heapq.heapreplace(heap, (freq, num))
    
    # 提取堆中的元素
    return [num for freq, num in heap]

6. 其他解法（桶排序）

另一种 O(n) 解法是桶排序（Bucket Sort）：

• 创建长度为 n+1 的数组 buckets，buckets[i] 存储出现频率为 i 的所有数字。
• 从高频率向低频率遍历，收集 k 个元素。

这种方法在 n 很大但不同数字很少时也高效。

7. 总结

• 核心：哈希表统计 + 最小堆维护 Top K。
• 时间复杂度：O(n log k)，优于 O(n log n)。
• 空间复杂度：O(n) 用于哈希表与堆。

这样就能高效解决「前 K 个高频元素」问题。