如何用 Quickselect 在含重复值的数组中找第 k 大元素？

题干与适用场景

给定未排序整数数组 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] 就返回枢轴值。三路分区让“全是相同值”的输入一次结束，不会因重复值退化为单边递归。

python

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 的最小堆；若需要任意秩查询，则考虑带子树大小的平衡树，并根据更新与查询比例评估实现成本。

编程面试：用 Quickselect 查找含重复值数组的第 k 大元素

题干