Python算法训练序列

数组与哈希 · Unit 05

← Unit 04
347
LeetCode 347Top K Frequent Elements · 前 K 个高频元素

统计完频次以后，
如何只拿走最重要的 K 个？

前几个单元学会了构造频次映射。Unit 05 继续追问：如果只需要频次最高的 k 个元素，是否还要把所有元素完整排序？桶排序利用“频次一定在 1 到 n 之间”直接按频次分层。

LeetCode #347 原题内容 中文转述 · 保留示例、约束与复杂度要求

题目要求

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

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # 在这里提交答案

约束

  • 1 ≤ len(nums) ≤ 100000
  • -10000 ≤ nums[i] ≤ 10000
  • 1 ≤ k ≤ 不同元素数量
  • 题目保证答案唯一；算法应优于完整排序的 O(n log n)。

示例

nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
nums = [1], k = 1
输出：[1]
1. 找出高频元素
2. 避免完整排序
3. 频次倒排成桶
4. 代码联动
5. 小顶堆迁移
nums = [1,1,1,2,2,3]
k = 2
frequency：元素 → 出现次数尚未统计
frequency = {}
buckets：频次 → 元素列表尚未建桶
result
[]
当前阶段—
当前 num—
当前 frequency—
正在扫描的桶—
已收集数量0 / 2
补全桶排序提交代码卡住可查看参考答案
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
frequency =
buckets =
for num, count in frequency.items():
result = []
for count in range():
for num in buckets[count]:
result.append(num)
if :
return result
from collections import Counter class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: frequency = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for num, count in frequency.items(): buckets[count].append(num) result = [] for count in range(len(buckets) - 1, 0, -1): for num in buckets[count]: result.append(num) if len(result) == k: return result
为什么桶数组长度是 n+1？一个元素最少出现1次，最多出现n次，因此频次可以直接作为桶下标。下标0不会存放答案，但保留它能让频次与数组下标完全对齐。
代码—频次字典—桶—结果联动示例：[1,1,1,2,2,3], k=2
1from collections import Counter
2class Solution:
3 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
4 frequency = Counter(nums)
5 buckets = [[] for _ in range(len(nums) + 1)]
6 for num, count in frequency.items():
7 buckets[count].append(num)
8 result = []
9 for count in range(len(buckets)-1, 0, -1):
10 for num in buckets[count]:
11 result.append(num)
12 if len(result) == k:
13 return result
逐行播放，观察频次映射如何被倒排成桶，并从高频桶向低频桶收集答案。
完成代码联动后进入小顶堆迁移 补全正确、查看答案或播放完整轨迹后解锁。

迁移题：当 k 很小、希望只维护 k 个候选时

使用大小最多为 k 的小顶堆。每加入一个 (count, num)，若堆大小超过 k，就弹出频次最小的元素。最终堆中留下前 k 个高频元素。

本单元形成的算法Skill

当已经得到 对象 → 频次，但只需要最大的 k 个时，不必默认完整排序。若频次范围有明确上界，可将映射倒排为 频次 → 对象列表，再从最高频次向下扫描；若 k 很小，也可维护大小为 k 的小顶堆。

LeetCode #347Counter频次倒排桶排序 O(n)小顶堆 O(m log k)提前返回
#217 哈希集合是否出现过
#1 哈希映射出现在哪里
#242 频次统计出现多少次
#49 规范化分组按签名分桶
#347 当前：Top K只保留最重要结果