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

题目描述

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

示例 1：

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

示例 2：

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

解题思路

步骤1：理解问题本质

这个问题要求找出出现频率最高的 k 个元素。关键点在于：

• 需要统计每个数字出现的频率
• 然后根据频率进行排序
• 最后取前 k 个频率最高的元素

步骤2：统计频率

首先，我们需要统计每个数字出现的次数。使用哈希表（字典）是最自然的方法：

# 统计频率
freq_map = {}
for num in nums:
    freq_map[num] = freq_map.get(num, 0) + 1

对于示例 [1,1,1,2,2,3]，我们会得到：

• 1: 3次
• 2: 2次
• 3: 1次

步骤3：排序方法（直接但不够高效）

最直观的方法是按照频率排序：

# 按频率降序排序
sorted_items = sorted(freq_map.items(), key=lambda x: x[1], reverse=True)
# 取前k个元素
result = [item[0] for item in sorted_items[:k]]

时间复杂度分析：

• 统计频率：O(n)
• 排序：O(m log m)，其中 m 是不同数字的个数
• 总复杂度：O(n + m log m)

当 n 很大但不同数字很少时，这种方法效率不错。但我们可以做得更好。

步骤4：使用堆优化（更高效的方法）

我们不需要对整个数组排序，只需要前 k 个最大的元素。这提示我们可以使用最小堆：

思路：

1. 维护一个大小为 k 的最小堆
2. 堆中存储 (频率, 数字) 对
3. 当堆大小超过 k 时，弹出频率最小的元素
4. 最后堆中剩下的就是频率最大的 k 个元素

import heapq

def topKFrequent(nums, k):
    # 统计频率
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    # 使用最小堆
    min_heap = []
    for num, freq in freq_map.items():
        heapq.heappush(min_heap, (freq, num))
        # 保持堆的大小为k
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    # 提取结果
    result = []
    while min_heap:
        result.append(heapq.heappop(min_heap)[1])
    
    return result[::-1]  # 反转得到频率从高到低

时间复杂度分析：

• 统计频率：O(n)
• 堆操作：O(m log k)，其中 m 是不同数字的个数
• 总复杂度：O(n + m log k)

当 k 远小于 m 时，这种方法比全排序更高效。

步骤5：桶排序方法（最优解）

还有一种更巧妙的方法——桶排序：

思路：

1. 创建 n+1 个桶（索引 0 到 n）
2. 将数字放入对应频率的桶中
3. 从高频率桶开始取数字，直到取够 k 个

def topKFrequent(nums, k):
    # 统计频率
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    # 创建桶
    buckets = [[] for _ in range(len(nums) + 1)]
    
    # 将数字放入对应频率的桶中
    for num, freq in freq_map.items():
        buckets[freq].append(num)
    
    # 从高频率开始收集结果
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        if buckets[i]:
            result.extend(buckets[i])
        if len(result) >= k:
            break
    
    return result[:k]

时间复杂度分析：

• 统计频率：O(n)
• 桶排序：O(n)
• 总复杂度：O(n)

这是最优解，因为每个步骤都是线性的。

总结比较

关键要点

1. 问题转化：将"前k个高频"转化为频率统计和排序问题
2. 数据结构选择：哈希表统计频率，根据k的大小选择堆或桶排序
3. 边界情况：k=0，k=数组长度，所有数字频率相同等情况

这个题目很好地考察了对不同排序方法和数据结构的理解，是面试中的高频题目。