官方任务
给定整数数组 nums 与整数 k，返回出现频率最高的 k 个元素。答案可以按任意顺序返回。
nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
输出：[1,2]
nums = [1], k = 1
输出：[1]
输出：[1]
第6章｜二分、堆与优先队列
Unit 07 · LeetCode #215
← Unit 06
215
Kth Largest in an ArrayHeap · Quickselect · Partition
离线数据允许另一种选择：
不维护Top-K，只定位目标排名。
大小K最小堆仍然有效，但当全部数组已在内存中时，还可以通过Quickselect分区：把一个枢轴放到最终排序位置，只继续处理包含目标下标的一侧。
LeetCode #215 原题内容题面转述、策略比较与复杂度
题目要求
给定整数数组 nums 和整数 k，返回数组按降序排序后的第 k 大元素。它是排序位置上的第k大，不是第k个不同元素。
题目进一步询问：能否在不完整排序数组的情况下完成？
class Solution:
def findKthLargest(
self,
nums: List[int],
k: int
) -> int:
pass
约束
1 ≤ k ≤ nums.length ≤ 10⁵；-10⁴ ≤ nums[i] ≤ 10⁴；- 数组可以包含重复值。
官方示例
nums = [3,2,1,5,6,4], k = 2
输出：5
输出：5
nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4
输出：4
本页主方法
将第k大转换为升序目标下标 target=n-k，使用Quickselect反复分区。平均时间 O(n)，最坏 O(n²)；迭代原地分区的额外空间为 O(1)。大小K最小堆仍提供稳定的 O(n log k) 方案。
目标排名下标
升序数组中第k大位于下标 n-k。示例n=6、k=2，因此目标是升序index 4。
Partition 分区
选择pivot，使其左侧元素≤pivot、右侧元素>pivot；pivot到达最终排序位置。
Quickselect
分区后不递归处理两边，只继续处理包含目标排名的一侧，因此平均总工作量是线性的。
随机枢轴
固定劣质pivot可能连续只排除一个元素；随机选择可以降低反复出现极端分区的风险。
1. 第K大与目标下标
2. 排序、堆与Quickselect
3. Partition分区不变量
4. 只保留目标排名一侧
5. Python与真实轨迹
6. 高频元素迁移
nums=[3,2,1,5,6,4]，k=2点击第2大元素
left=0
scan=—
store=—
right=5
pivot=4
≤ pivot
pivot
4> pivot
当前排名证据
第2大在升序排列中对应index n-k=4。
Quickselect候选不变量
升序目标下标target=n-k始终位于当前索引区间[left,right]中。
完整排序时间O(n log n)
得到所有排名
得到所有排名
大小K最小堆时间O(n log k)
维护Top-K边界
维护Top-K边界
Quickselect平均O(n)
只定位目标排名
只定位目标排名
分区与区间记录
升序目标下标4
pivot最终下标—
目标相对pivot—
下一候选区间[0,5]
核心不变量
每次partition后，pivot已经位于完整升序排序中的最终下标；目标只可能在pivot处或其中一侧。
为什么不处理另一侧
我们只需要一个排名，不需要两侧内部有序。pivot下标已经提供足够的排名方向信息。
当前候选长度6
已完成分区0
本轮扫描元素0
本轮排除数量0
当前答案未确定
排序最简单；大小K堆适合k较小且需要稳定复杂度；Quickselect平均最快并可原地执行，但最坏分区会退化。
目标下标转换、partition范围以及分区后的方向判断必须保持一致。
错误一：target=k−1
k−1是降序下标；当前partition按升序放置pivot，因此目标必须是 n-k。
错误二：两侧都递归
两侧都处理会退回QuickSort式工作。选择问题只需继续包含target的一侧。
错误三：忽略最坏分区
固定末尾pivot遇到有序数组时可能每轮只减少一个元素，最坏达到O(n²)。
重复值分别占据排序位置；Quickselect不需要去重，也不要求pivot值唯一。
k=1
target=n−1
寻找最大值
target=n−1
寻找最大值
k=n
target=0
寻找最小值
target=0
寻找最小值
[3,2,3,1,2,4,5,5,6], k=4
重复5分别计入
答案4
重复5分别计入
答案4
补全Quickselect提交代码Lomuto升序分区
class Solution:
def findKthLargest(self, nums, k) -> int:
target =
left, right = 0, len(nums) - 1
while left <= right:
pivot = nums[right]
store =
for scan in range(left, right):
if :
nums[store], nums[scan] = nums[scan], nums[store]
nums[store], nums[right] = nums[right], nums[store]
if store == target:
return
if store < target:
else:
提示 1｜先统一排名方向
当前 partition 按升序放置 pivot，因此第 k 大要先转成升序目标下标。
提示 2｜store 的语义
提示 3｜扫描更新
只有当前元素应进入左分区时，才交换到 store 并扩展左分区。
提示 4｜pivot 落位
扫描结束后把 pivot 交换到 store；此时 store 是 pivot 的最终升序排名。
提示 5｜只保留一侧
比较 store 与 target：相等返回；store 偏左则移动 left；偏右则移动 right。
当前 partition 按升序放置 pivot，因此第 k 大要先转成升序目标下标。
提示 2｜store 的语义
[left, store) 已经全部不大于 pivot；store 指向下一个可放入左分区的位置。提示 3｜扫描更新
只有当前元素应进入左分区时，才交换到 store 并扩展左分区。
提示 4｜pivot 落位
扫描结束后把 pivot 交换到 store；此时 store 是 pivot 的最终升序排名。
提示 5｜只保留一侧
比较 store 与 target：相等返回；store 偏左则移动 left；偏右则移动 right。
稳定替代方案：Unit 06 的大小K最小堆可直接复用，时间O(n log k)、空间O(k)。生产代码若更看重最坏性能可预测性，堆方案通常更稳；Quickselect适合离线、允许修改数组且追求平均线性时间的场景。
代码—扫描边界—pivot位置—候选侧联动示例[3,2,1,5,6,4], k=2
1class Solution:
2 def findKthLargest(self, nums, k):
3 target = len(nums) - k
4 left, right = 0, len(nums)-1
6 while left <= right:
7 pivot = nums[right]
8 store = left
10 for scan in range(left, right):
11 if nums[scan] <= pivot:
12 swap(nums[store], nums[scan])
13 store += 1
15 swap(nums[store], nums[right])
17 if store == target:
18 return nums[store]
20 if store < target:
21 left = store + 1
23 right = store - 1
第一轮pivot=4落到index 3，目标index 4在右侧；第二轮处理[6,5]，pivot=5落到index 4并命中。
完成代码联动后进入Top-K频率迁移只有主代码正确或完整播放 Quickselect 轨迹后解锁；提示与骨架不计为掌握。
Progressive Transfer · LeetCode #347
迁移题：前 K 个高频元素
本题不是直接比较原始数值，而是先把数组压缩成 元素 → 出现频率 的候选集合，再维护频率最高的 K 个元素。返回顺序可以任意。
约束与性能要求
1 ≤ nums.length ≤ 10⁵-10⁴ ≤ nums[i] ≤ 10⁴1 ≤ k ≤ 不同元素数量- 题目保证答案唯一
- 目标复杂度优于完整排序的
O(n log n)
读题门槛
示例中元素 1、2、3 的频率分别是多少？
返回结果必须按频率从高到低排序吗？
两题都正确后开放结构映射。
比较标准是数值大小；Quickselect 直接在原数组中定位目标排名。
先用哈希表压缩重复值，再按 frequency 维护 Top-K。
保留的不变量：大小 K 的最小堆保存当前频率最高的 K 个候选；堆顶是这 K 个候选中频率最低者，也是下一次最可能被淘汰的边界。
排列算法依赖顺序
点击下列步骤，将它们加入执行序列。
尚未选择
完成四个语义槽位
不要求背完整代码，只要求把“计数 → 候选 → 容量约束 → 提取结果”四个职责写准确。
官方样例轨迹
nums=[1,1,1,2,2,3], k=2
步骤 1/7
大小 K 的最小堆
尚未形成边界
完整运行样例后开放独立重写。
独立实现 #347
第6章 Unit 07 Skill卡
离线第K大可以选择完整排序、大小K堆或Quickselect。Quickselect的关键不是让数组完全有序，而是让pivot获得确定排名，并只继续处理包含目标下标的一侧。
题号与题型#215｜离线选择与Top-K策略比较
排名转换第k大→升序目标下标n-k
Partition不变量左侧≤pivot，pivot在最终位置，右侧>pivot
方向判断pivotIndex<target向右；大于target向左
停止条件pivotIndex==target时直接返回pivot
重复值按排序位置计入，不去重
复杂度Quickselect平均O(n)、最坏O(n²)、迭代额外O(1)
方案选择排序最简单；堆更稳定；Quickselect平均更快且原地
推荐下一题#347 前K个高频元素