第6章｜二分、堆与优先队列

Unit 08 · LeetCode #347

← Unit 07
347
Top K Frequent ElementsHash Map · Heap · Bucket Sort

先把重复数据压缩成频率候选，
再在候选之间维护 Top-K。

原数组中的每次出现并不是独立候选。第一步用哈希表将数组压缩为 value → frequency；第二步才按照频率选择最大的K个不同元素。

LeetCode #347 原题内容题面转述、频率候选与复杂度

题目要求

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

题目保证答案唯一，并要求算法时间复杂度优于 O(n log n)。

class Solution: def topKFrequent( self, nums: List[int], k: int ) -> List[int]: pass

约束

  • 1 ≤ nums.length ≤ 10⁵；
  • -10⁴ ≤ nums[i] ≤ 10⁴；
  • 1 ≤ k ≤ 不同元素数量；
  • 答案集合保证唯一。

官方示例

nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
nums = [1], k = 1
输出：[1]
nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]

本页两种方法

通用堆方案：计数后维护大小K的最小堆，时间 O(n+m log k)、空间 O(m+k)。

主提交方案：按频率建桶并从高频向低频扫描，时间和空间均为 O(n)。其中 m 是不同元素数。

频率候选

候选单位从“数组中的每个位置”变成“每个不同元素及其频率”。同一值只产生一个候选。

复合记录

堆中保存 (frequency,value)。堆的优先级由频率决定，返回结果则提取value。

频率桶

频率最多为n，可建立 buckets[freq] 保存恰好出现freq次的所有元素。

Top-K集合

题目返回的是K个元素，而不是第K大的单个频率。达到K个结果后即可停止。

1. 原始数组压缩为频率表
2. 频率候选与Top-K堆
3. 插入、超容量与淘汰
4. 频率桶与线性扫描
5. Python与真实轨迹
6. K个最近点迁移
nums=[1,1,1,2,2,3]，k=2先建立频率候选

大小K最小堆

频率桶 buckets[freq]

频率表尚未完成。
当前候选解释

同一数值的多次出现应先聚合为一个频率候选。

两阶段契约 frequency[value]等于已扫描前缀中value的出现次数。
频率排名元素频率Top-K

计数与候选更新记录

不同元素数m3
当前候选—
堆顶边界频率—
已收集结果数0 / 2

堆方法不变量

处理完每个频率候选后，大小K最小堆保存当前频率最高的K个元素；堆顶是其中最低频边界。

桶方法为什么能线性

频率是 1…n 的整数。无需比较排序，直接按频率作为数组下标，再从n向1扫描。

原始元素数量n6
不同元素数量m3
当前堆大小0
当前扫描频率—
当前结果[]
排序、最小堆和桶排序维护的信息不同

完整排序比较所有候选；最小堆只维护前K频率边界；桶排序利用频率是有限整数这一额外结构，避免候选间比较。

原数组Top-K与频率Top-K是两个不同问题

必须先完成候选压缩，再选择优先级；否则容易把数值大小、出现位置或重复副本误当作排名标准。

错误一：直接选最大数值

示例中数值3最大，但只出现1次；高频元素是1和2。

错误二：把三个1作为三个候选

返回要求是不同元素。三个1应压缩成候选 (3,1)。

错误三：桶长度只建m+1

频率上限由原数组长度n决定，而不是不同元素数量m。

答案唯一不等于频率全部不同

边界之外可以存在相同频率；只要不存在导致多个不同Top-K集合的边界歧义，题目就保证唯一答案。

nums=[1], k=1
frequency={1:1}
返回[1]
k=不同元素数
所有候选都返回
顺序任意
负数同样可作哈希键
频率逻辑不变
补全LeetCode提交代码频率桶O(n)
class Solution:
def topKFrequent(self, nums, k):
frequency =
buckets =
for value, count in frequency.items():
result = []
for count in range():
for value in buckets[count]:
if len(result) == k:
return
return result
提示与骨架不会解锁迁移
提示 1｜先把原数组压缩成 value → count，后续选择只遍历不同元素。
提示 2｜桶下标就是频率，因此桶数量由最大可能频率 n 决定。
提示 3｜候选 (value,count) 应进入 buckets[count]。
提示 4｜Top-K 高频必须从 n 向 1 扫描，而不是从低频向高频。
提示 5｜收集到第 k 个元素时立即返回，低频桶不会再改变答案集合。
策略对照：频率桶利用“优先级是 1…n 的有限整数”实现线性扫描；当优先级不能直接作为数组下标时，回到大小 K 的边界堆。这里不展开完整替代代码，重点是先决定候选与优先级，再选择数据结构。
代码—频率表—桶索引—结果集合联动示例[1,1,1,2,2,3]
1class Solution:
2 def topKFrequent(self, nums, k):
3 frequency = Counter(nums)
4 buckets = [[] for _ in range(n+1)]
6 for value, count in frequency.items():
7 buckets[count].append(value)
9 result = []
11 for count in range(n, 0, -1):
12 for value in buckets[count]:
13 result.append(value)
15 if len(result) == k:
16 return result
轨迹先得到frequency={1:3,2:2,3:1}，再将1放入桶3、2放入桶2、3放入桶1，最后从频率6向下扫描并收集1、2。
完成代码联动后进入最近点迁移主代码正确或播放完整轨迹后解锁。提示与骨架不计为掌握。

迁移题：LeetCode #973 最接近原点的 K 个点

候选从“不同元素”变成“二维点”，优先级从频率变成平方距离。保留方向由最大优先级反转为最小优先级，因此边界堆的方向也必须反转。

1. 官方读题
2. 结构映射
3. 语义槽位
4. 样例与重写

官方原题

给定二维点数组 points，其中 points[i]=[xᵢ,yᵢ]，返回距离原点 (0,0) 最近的 k 个点。答案顺序任意，除顺序外答案保证唯一。

  • 欧氏距离为 √(x²+y²)；比较时可直接使用平方距离。
  • 1 ≤ k ≤ points.length ≤ 10⁴。
  • -10⁴ ≤ xᵢ,yᵢ ≤ 10⁴。
打开 LeetCode #973 官方题面 ↗

官方示例

points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
反向顺序同样有效
状态检查 1｜第一组示例中哪个点更近？
状态检查 2｜返回的 K 个点必须按距离排序吗？
完成两道读题检查后开放结构映射。

#347｜保留最大频率

候选：不同元素
优先级：frequency
保留：最大的 K 个优先级
边界：Top-K 中最低频
结构：大小 K 最小堆

#973｜保留最小距离

候选：二维点
优先级：x²+y²
保留：最小的 K 个优先级
边界：K 个最近点中最远者
结构：大小 K 最大堆；Python 用负距离模拟

按依赖顺序组装 #973

从“为点计算可比较优先级”开始。
heap = [] for x, y in points: distance = x * x + y * y heapq.heappush(heap, (-distance, x, y)) if len(heap) > k: heapq.heappop(heap) return [[x, y] for _, x, y in heap]
每个槽位都必须表达一种语义，而不是照抄完整答案。

官方样例轨迹

当前候选—
平方距离—
本轮淘汰—
保留结果[]
从空堆开始扫描三个点。

负距离堆视图

最小堆根保存最小的负距离，也就是绝对距离最大的保留候选。

独立重写

不提供占位符。请独立实现大小 K 的最远边界堆。

第6章 Unit 08 Skill卡

前K高频元素包含两个独立设计：用哈希表决定候选是什么，用堆或频率桶决定如何选择Top-K。数据的优先级若是有限整数，还可以用桶下标替代比较排序。

题号与题型#347｜哈希计数＋Top-K选择
候选压缩原数组→不同元素的(value,frequency)候选
堆不变量大小K最小堆保存频率最高的K个候选
堆顶含义Top-K中频率最低的淘汰边界
桶结构buckets[freq]保存出现freq次的元素
桶扫描从n向1收集，达到K个元素立即返回
复杂度桶排序时间O(n)、空间O(n)
常见错误按数值Top-K；不压缩重复值；桶长度使用m+1
推荐下一题#973 最接近原点的K个点