347. 前 K 个高频元素 (Medium)
专题归类： 06-栈与堆 · 01-哈希表 LeetCode 链接： https://leetcode.cn/problems/top-k-frequent-elements/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
题目详细分析
- 数据范围： 1 ≤ nums.length ≤ 10^5，k 的取值范围是 [1, 数组中不相同的元素的个数]，题目保证答案唯一（即前 k 个高频元素是唯一的）。
- 输入输出特征： 返回频率最高的 k 个元素，顺序不限。输入包含整数（可能重复），输出无顺序要求。
- 边界条件：
- k = 1 → 返回出现频率最高的那个元素。
- k = 不重复元素数量 → 返回所有不重复元素。
- 所有元素相同 → 返回任意 k 个（其实就是那个元素）。
- 核心约束： 时间复杂度必须优于 O(n log n)。这意味着不能对整个数组按频率排序。
- 隐藏条件：
- 需要两步走：先统计频率，再从频率中选 Top K。
- 频率统计可以用哈希表（Counter）实现 O(n)。
- 选 Top K 可以用最小堆 O(n log k) 或桶排序 O(n)。
- 题目保证答案唯一，但频率可能相同（在 Top K 边界上频率相同的情况不出现）。
小白版直白理解
就像统计一个班级里最流行的几个兴趣爱好。
第一步，班长发一张表统计每个人的兴趣，得到每个兴趣有多少人选了（这就是频率统计）。
第二步，找出最热门的 k 个兴趣。效率最高的方式是：拿着一个只有 k 个位置的”排行榜”，上面只记录当前最热门的 k 个兴趣。每来一个兴趣，就把它和排行榜上最不热门的比较，如果更热门就替换掉。最后排行榜上就是前 k 个最热门的兴趣。
这个”排行榜”就是 最小堆——堆顶永远是最不热门的那个，方便随时替换。
另一种更快的方式（桶排序）：既然频率范围有限，那就把相同频率的兴趣放在同一个桶里，从高频率往低频率拿，直到拿到 k 个为止。
解题思路
思路一：哈希表 + 最小堆（推荐）
核心思想： 先用 Counter 统计每个数字的频率，然后构建一个大小为 k 的最小堆（按频率排序）。堆中始终保持当前频率最高的 k 个元素。
为什么用最小堆不是最大堆？因为我们要保留前 k 高的元素，用最小堆可以把堆顶（最小的频率）弹出，而较大的频率留在堆中。如果用最大堆，我们需要把所有元素都入堆，复杂度为 O(n log n)。
from collections import Counter
import heapq
def topKFrequent(nums, k):
# 1. 频率统计 O(n)
count = Counter(nums)
# 2. 最小堆维护 Top K
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num)) # 按频率排序
if len(heap) > k:
heapq.heappop(heap) # 弹出频率最低的
# 3. 提取结果
return [num for _, num in heap]复杂度： 时间 O(n log k)，空间 O(n)
思路二：桶排序（当 n 与频率范围相近时更高效）
核心思想： 创建一个列表 bucket，其中 bucket[i] 存储出现频率为 i 的所有元素。然后从高频率向低频率遍历，收集前 k 个元素。
这种方法利用了频率最大值为 n 的约束，用 O(n) 空间换时间。
from collections import Counter
def topKFrequent(nums, k):
# 1. 频率统计
count = Counter(nums)
# 2. 桶排序：频率 → 元素列表
n = len(nums)
bucket = [[] for _ in range(n + 1)]
for num, freq in count.items():
bucket[freq].append(num)
# 3. 从高到低收集结果
result = []
for freq in range(n, 0, -1):
for num in bucket[freq]:
result.append(num)
if len(result) == k:
return result复杂度： 时间 O(n)（严格 O(n)），空间 O(n)
思路三：快速选择（Quick Select）
和 215 题一样，可以对频率数组使用快速选择算法找到第 k 大的频率位置，但实现较复杂。
from collections import Counter
import random
def topKFrequent(nums, k):
count = Counter(nums)
unique = list(count.items()) # [(num, freq), ...]
def partition(l, r):
pivot = unique[random.randint(l, r)][1]
# 将 pivot 移到右边
p_idx = l
for i in range(l, r + 1):
if unique[i][1] == pivot:
p_idx = i
break
unique[p_idx], unique[r] = unique[r], unique[p_idx]
i = l
for j in range(l, r):
if unique[j][1] > unique[r][1]:
unique[i], unique[j] = unique[j], unique[i]
i += 1
unique[i], unique[r] = unique[r], unique[i]
return i
l, r = 0, len(unique) - 1
k -= 1
while True:
pos = partition(l, r)
if pos == k:
break
elif pos < k:
l = pos + 1
else:
r = pos - 1
return [unique[i][0] for i in range(k + 1)]复杂度： 平均 O(n)，最坏 O(n²)
易错点
- 堆中存储的是元组 (freq, num)： 需要按频率排序，所以元组的第一个元素必须是频率。Python 的 heap 默认按元组第一个元素排序。
- 最小堆保留的是高频元素： 每次弹出的是堆顶（最小频率），最后堆中留下的就是频率最高的 k 个。不要把逻辑搞反。
- 桶排序的索引范围： 频率最大为 n（所有元素相同），所以桶数组大小为 n+1（索引从 0 到 n）。频率 0 的桶永远为空。
- Counter 与手动 dict 的取舍：
collections.Counter是最方便的选择，但面试中有时会要求手动实现来展示基本功。 - 结果的顺序： 题目不要求顺序，所以直接返回列表即可。
框架提炼
Top K 频率模板（最小堆）：
from collections import Counter
import heapq
def top_k_frequent(elements, k):
"""返回出现频率前 k 高的元素"""
# 1. 统计频率
freq = Counter(elements)
# 2. 最小堆选 Top K
heap = []
for elem, count in freq.items():
heapq.heappush(heap, (count, elem))
if len(heap) > k:
heapq.heappop(heap)
return [elem for _, elem in heap]Top K 问题解法谱系：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 排序全数组 | O(n log n) | O(1) | 数据量小 |
| 堆 | O(n log k) | O(n + k) | 通用，k 较小 |
| 桶排序 | O(n) | O(n) | 频率范围已知且不大 |
| 快速选择 | O(n) 平均 | O(n) | 追求理论最优 |
关联题目
- 215-数组中的第K个最大元素 — 本题的简化版（没有频率统计步骤，直接对数值找 Top K）。两题解法相通，堆和快速选择都可复用。
- 295-数据流的中位数 — 堆的另一个经典应用：双堆维护中位数。347 是用一个堆维护 Top K，295 是用两个堆维护中位数。
- 692-前K个高频单词 — 完全相同的题目，但元素是字符串，且要求按字母序排列。同样可以用堆或桶排序解决。