题干与适用场景
给定未排序整数数组 nums 和 1 ≤ k ≤ nums.length，返回按非递增排序后的第 k 个元素。重复值按多个位置计数，例如 [5, 5, 4] 的第 2 大是 5，不是第 2 大的不同值。目标是平均 O(n) 时间、原地 O(1) 额外空间；面试中应先说明随机输入和可否修改数组。
面试官考察点
强回答会先把“第 k 大”转换为升序下标 target = n-k，再解释 partition 只需保证枢轴左侧不大于它、右侧不小于它，未命中的一侧无需继续排序。还要说清重复值、k=1、k=n、已排序输入，以及随机枢轴对最坏情况的影响。
回答前需要澄清的问题
- 是否允许修改输入？允许时可原地 partition；不允许时需复制数组，空间变为
O(n)。 - 要第 k 大还是第 k 个不同值？前者直接按位置计数；后者必须跳过重复值，算法和题意不同。
- 是否有持续流入的数据？单次数组适合 Quickselect；流式场景通常用大小为
k的最小堆，复杂度为O(n log k)。 - 是否必须有确定的最坏线性界？普通随机 Quickselect 只有平均
O(n)；严格保证需 median-of-medians 或库函数的实现保证。
推荐解法与推导
使用三路 partition：把区间分成「小于 pivot」「等于 pivot」「大于 pivot」。对第 k 大转换后的升序下标 target，若目标位置在 lt 左侧只处理左区间；若在 gt 右侧只处理右区间；落在 [lt, gt] 就返回枢轴值。三路分区让“全是相同值”的输入一次结束，不会因重复值退化为单边递归。
import random
def kth_largest(nums: list[int], k: int) -> int:
if not 1 <= k <= len(nums):
raise ValueError("k out of range")
target = len(nums) - k
left, right = 0, len(nums) - 1
while left <= right:
pivot = nums[random.randint(left, right)]
lt, i, gt = left, left, right
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1; i += 1
elif nums[i] > pivot:
nums[i], nums[gt] = nums[gt], nums[i]
gt -= 1
else:
i += 1
if target < lt:
right = lt - 1
elif target > gt:
left = gt + 1
else:
return pivot
raise RuntimeError("unreachable")每轮扫描当前区间一次。若枢轴把区间按期望比例缩小，递推为 T(n)=T(cn)+O(n)，总计平均 O(n)；随机枢轴仍可能连续选到极值，最坏为 O(n²)。循环写法避免递归栈，额外空间为 O(1)。
替代方案与权衡
完整排序最容易验证，时间 O(n log n)，当数组很小或后续还要完整顺序时更合适。大小为 k 的最小堆不修改数组，单次扫描为 O(n log k)、空间 O(k)，适合流式数据或 k 远小于 n。C++ 的 std::nth_element 表达同一语义并只保证平均线性复杂度；面试中可以调用它，但仍应说明分区不保证前后两段有序。
失败场景、边界与反例
- 把
target写成k-1会求第 k 小，方向完全相反。 - 用单向二路分区处理
[7,7,7,...]，若每次只排除一个元素会达到O(n²)；三路分区一次吞掉等值段。 - 直接固定取
right为枢轴，在已排序或反向排序输入上可稳定退化；随机化降低触发概率，但没有确定性最坏界。 - 返回“第 k 大不同值”不能复用上述停止条件，必须在等值段计数或先去重。
- 空数组、
k=0、k>n应在入口拒绝，不能让下标错误掩盖题意问题。
测试与验证清单
至少运行以下性质测试：随机数组与 sorted(nums)[-k] 对比；全相同数组；含负数和重复值；k=1 与 k=n；已排序和反向排序数组；输入被允许修改时检查返回值而非数组顺序。再用固定随机种子复现实验，观察比较次数随 n 的增长，避免把一次幸运运行当成复杂度证明。
追问与延伸
如何保证最坏情况仍为线性？
使用 median-of-medians 选枢轴，使每轮删除固定比例，得到 O(n) 最坏时间；代价是常数更大，工程代码通常倾向随机化或标准库实现。
如何改成第 k 小？
把目标下标改成 k-1，比较方向保持升序 partition；也可直接对第 k 大问题使用 target=n-k，避免在代码中反转数组。
如何支持动态插入和多次查询？
单次 Quickselect 会重复扫描。若只维护一个固定 k，可保留大小为 k 的最小堆；若需要任意秩查询，则考虑带子树大小的平衡树，并根据更新与查询比例评估实现成本。