题目与适用场景
给定整数数组 nums 和整数 k，返回按排序位置计算的第 k 大元素，而不是第 k 个不同元素。假设 1 <= k <= nums.length <= 100,000，且 -10,000 <= nums[i] <= 10,000。
例如，nums = [3, 2, 1, 5, 6, 4]、k = 2 时返回 5。对于 nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]、k = 4，答案是 4：相同数值会占据多个排序位置。
这是有代表性的顺序统计量算法题。完整排序、大小为 k 的最小堆和快速选择在不同约束下都成立。本文主解法使用随机化三向快速选择，因为输入是内存中的可变数组，且只查询一个排名。实现会修改 nums；如果调用方要求保留原数组，应先复制并计入额外空间。
面试官在考察什么
第一个信号是能否说清契约。“第 k 大”表示降序排序中的第 k 个位置，重复值也参与计数。它不表示第 k 个不同值、最大的 k 个值，也不表示零下标数组中的索引 k。转换为升序后，目标的零下标索引是 n - k。
第二个信号是能否推导不同方案，而不是直接背快速选择。排序是 O(n log n) 的稳妥基线；大小为 k 的最小堆用 O(n log k) 时间和 O(k) 空间，也适合流式输入；快速选择丢弃不可能包含目标的分区，期望时间为 O(n)，但随机化主元并不会消除 O(n^2) 最坏情况。
第三个信号是能否明确分区不变量。代码“看起来像快速排序”并不足够。候选人应说明 lt 之前、lt 到 i、i 到 gt、gt 之后分别已知什么，并解释缩小后区间为何仍包含目标排名。
最后还会考察重复值、输入修改契约、非法输入行为、用迭代避免递归深度风险，以及能否用简单正确的基准答案做对照测试。只有优化代码，没有证明边界和对抗用例，回答仍不完整。
回答前应澄清的问题
- 第 k 大是否计算重复值？ 本文按排序位置计算，因此
[5, 5, 4]的第 2 大是5。若要求不同值排名，就需要先去重或按频次选择。 k是否保证有效，数组能否为空？ 题设保证1 <= k <= n。独立实现仍会对越界参数抛出ValueError，让契约明确。- 可以修改输入数组吗？ 原地分区只需
O(1)辅助空间。禁止修改时先复制，额外空间变为O(n)。 - 输入完整存在，还是持续到达？ 快速选择要求随机访问和修改；无界数据流更适合大小为
k的最小堆。 - 只查询一次，还是对同一数据查询多个排名？ 单次查询适合快速选择；后续查询很多时，一次排序的
O(n log n)成本可能更划算。 - 数值范围是否真的小且固定？ 题设只有 20,001 个可能整数，因此计数法可用
O(n + R)时间、O(R)空间解决，R为值域宽度；数值无界时不能把它当通用方案。 - 是否必须保证最坏时间？ 随机化快速选择是期望线性时间。若要求确定性最坏线性时间，应讨论中位数的中位数；也可以选择更易实现、时间可预测的
O(n log k)堆方案。
30 秒回答框架
“重复值按排序位置计数，所以第 k 大对应升序索引 n - k。排序是简单的 O(n log n) 基线；大小为 k 的最小堆适合流式或不可修改输入，时间是 O(n log k)。本题只查一个排名且数组可修改，我会用迭代的随机化快速选择。每轮按随机主元分成小于、等于和大于三段；n - k 落在等值段就返回主元，否则只保留包含目标索引的一侧。三向分区能让重复值很多的输入一次跳过整个等值段。期望时间 O(n)，最坏 O(n^2)，辅助空间 O(1)。我会用排序结果作为 oracle，对全相等、已排序、逆序、重复值密集、边界 k 和随机数组做验证。”
分步深入回答
先建立基准答案。升序排序后返回 sorted(nums)[len(nums) - k]，最容易解释，也能确认排名换算。若为了保留原数组而复制，复杂度是 O(n log n) 时间和 O(n) 空间。它还可作为后续随机测试的正确性 oracle。
当 k 较小或数据逐条到达时，固定大小堆更合适。把每个值压入最小堆；堆大小超过 k 时弹出最小值。处理结束后，堆顶是最大 k 个值中最小的一个，也就是第 k 大。堆最多保存 k 个值，因此时间为 O(n log k)、空间为 O(k)。如果 k 接近 n 且完整数组已经在内存中，这个优势会缩小。
快速选择利用“只关心一个最终位置”这一点。先把降序排名换成 target = len(nums) - k。每轮在活动区间 [left, right] 随机选择主元值，并做荷兰国旗式三向分区。扫描期间保持：
[left, lt)全部小于主元。[lt, i)全部等于主元。[i, gt]尚未分类。(gt, right]全部大于主元。
扫描完成后，[lt, gt] 是完整等值段。若 target < lt，继续搜索较小值一侧；若 target > gt，继续搜索较大值一侧；否则目标位于等值段，主元就是答案。对 [7, 7, 7, 7] 这类输入，普通二向分区可能反复剥离极少元素，三向分区一次扫描即可返回。
import random
def find_kth_largest(nums: list[int], k: int) -> int:
if not 1 <= k <= len(nums):
raise ValueError("k must be between 1 and len(nums)")
target = len(nums) - k
left = 0
right = len(nums) - 1
while left <= right:
pivot = nums[random.randrange(left, right + 1)]
lt = left
i = left
gt = 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 for a valid k")i 的递增故意不对称。大于主元的值与 nums[gt] 交换后，新进入 i 的值尚未分类，因此 i 不能移动；小于主元的值向左交换后，相关位置的类别都已确定，所以 lt 和 i 同时递增。
正确性来自不变量和排名排除。分区保留全部输入元素，并让小值位于等值段之前、大值位于等值段之后，因此 [lt, gt] 中每个升序位置的值都等于主元。目标在等值段外时，被丢弃的一侧和等值段都不可能占据目标索引；保留区间仍包含答案。每轮要么返回，要么严格缩短区间，因此合法目标最终必然被返回。
每次分区只扫描当前区间一次。随机主元下，连续保留区间的期望总工作量为 O(n)。若连续选到极端主元，区间可能依次只有 n - 1、n - 2 个元素，最坏时间为 O(n^2)。实现使用循环和原地分区，辅助空间为 O(1)；这里不把输入数组和随机数生成器状态计入辅助存储。
测试应使用排序 oracle，而不只检查固定示例：
def oracle(nums: list[int], k: int) -> int:
return sorted(nums)[len(nums) - k]
cases = [
([3, 2, 1, 5, 6, 4], 2),
([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
([1], 1),
([7, 7, 7, 7], 3),
([-5, -1, -3, -1], 2),
(list(range(1000)), 1),
(list(range(1000)), 1000),
]
for values, rank in cases:
assert find_kth_largest(values.copy(), rank) == oracle(values, rank)再生成大量重复值数组，对每个合法 k 与 oracle 比较；同时断言 k = 0、k > n 和空数组会抛出约定错误。固定随机种子可以复现失败用例，多组种子则覆盖不同分区路径。
高质量示范回答
“我先确认重复值会占据多个排序位置，并假设 k 有效。若数组升序排列，答案索引是 n - k。最简单方案是排序后取值，时间 O(n log n)；流式数据可维护大小为 k 的最小堆，时间 O(n log k)。
本题只有一次查询且允许修改数组，我会用随机化快速选择。在当前区间随机取主元，把元素分成小于、等于和大于三段。三向分区很重要，因为重复值应占多个排名，而且全相等输入应在一次分区后结束。分区完成后，如果 n - k 落在等值段就返回主元，否则只保留包含目标索引的一侧并迭代。
扫描不变量是：lt 前都更小，lt 到 i 都相等，gt 后都更大，中间仍未分类。这能证明最终等值段对应正确的排序排名区间，保留的一侧继续包含答案。
随机主元下期望时间是 O(n)，最坏仍为 O(n^2)；循环和原地分区只用 O(1) 辅助空间。我会明确函数会修改输入，并用排序 oracle 对生成数组做对照，覆盖重复值、全相等、已排序、逆序、负数、k = 1 和 k = n。”
常见错误
- 返回第 k 个不同值 → 契约按排序位置计算重复值 → 直接转换为升序索引
n - k，不要去重。 - 在升序数组使用索引
k或k - 1→ 排名方向转换错误 → 检查k = 1应映射到n - 1，k = n应映射到0。 - 把最小堆复杂度写成
O(n log n)→ 堆始终不超过k个元素 → 写明O(n log k)时间和O(k)空间。 - 同时递归两个分区 → 退化为快速排序的工作量 → 只进入包含
target的区间。 - 固定选第一个或最后一个主元 → 有序或构造输入可连续产生大小为
n - 1的区间 → 随机选择主元，并保留最坏情况说明。 - 使用二向分区却不讨论重复值 → 重复值密集时进展很差 → 建立完整等值段，目标落入时立即返回。
- 与
gt交换后仍递增i→ 新换入的值尚未分类，会被跳过 → 保持i不动直到该值完成分类。 - 声称随机化保证线性时间 → 仍可能连续遇到差主元 → 表述为期望
O(n)、最坏O(n^2)。 - 不说明会修改输入 → 调用方可能依赖原顺序 → 公开修改契约，或复制并计入
O(n)空间。 - 只测试两个示例 → 无法发现排名偏移、重复值和分区错误 → 用排序 oracle 覆盖边界、结构化和随机输入。
追问与应对方式
追问 1：如果输入是无界数据流，方案如何变化？
完整的随机访问数组不存在，快速选择不再适用。维护最多 k 个值的最小堆：未满时压入，已满后只在新值更大时替换堆顶。堆顶始终是当前第 k 大。单次更新 O(log k)、查询 O(1)、空间 O(k)。若 k 也任意变化，现有状态可能不足，需要更丰富的有序结构或保留原始数据。
追问 2：如果函数必须保留输入数组呢？
最直接的方法是复制为 working = nums.copy() 后执行快速选择，辅助空间变为 O(n)。大小为 k 的堆只用 O(k) 空间且不修改输入，k 较小时可能更合适。若 n 不大或后续有多次排名查询，排序副本通常更简单。
追问 3：能否保证最坏线性时间？
中位数的中位数能够选择一个在最坏情况下排除固定比例元素的主元，从而实现确定性 O(n) 选择。它的实现和常数更大，所以除非题目明确要求最坏上界，面试中通常优先随机化快速选择。固定大小堆则提供更易实现、可预测的 O(n log k) 方案。
追问 4：如何利用题设中的小整数值域？
为 -10,000 到 10,000 建立频次数组，扫描输入计数，再从高到低遍历桶并从 k 中扣减频次；第一个包含剩余排名的桶就是答案。值域宽度 R = 20,001 时，时间 O(n + R)、空间 O(R)。它是确定性的，也自然处理重复值，但值域很大或无界时不再适合。
追问 5：如果要求返回排好序的最大 k 个元素呢？
输出目标已经不只是一个顺序统计量。大小为 k 的堆最后再排序，时间为 O(n log k + k log k)、空间 O(k)。也可以先快速选择分出最大的 k 个值，再排序该部分，期望时间 O(n + k log k)。应根据是否允许修改、内存、最坏时间要求和输出是否必须有序选择。
追问 6：如何让随机化测试失败可以复现？
给函数注入随机数生成器，或在每次测试前固定种子；失败时记录种子、输入和 k。同一输入用多组固定种子运行，并始终与排序 oracle 对照。这样既能复现某条主元路径，也能确认错误是否跨路径存在。