LC215　数组中的第K个最大元素¶

中等通过率 60%python3核心代码模式堆样例通过牛客 AC数组分治快速选择排序堆（优先队列）

一句话

快速选择：只递归到目标所在的那一侧，期望 O(n)。

解题思路¶

这题考什么¶

题面点名要求 O(n)，这就排除了「排序后取第 k 个」（O(n log n)）和「维护大小为 k 的小顶堆」（O(n log k)）。

快速选择（quickselect）是快排的「半边版本」。快排划分之后要递归处理两侧，但求第 k 个元素时，划分完就能知道目标落在哪一侧——另一侧根本不用管。每轮期望把待处理区间砍掉一半，总代价 n + n/2 + n/4 + … < 2n，于是是 O(n)，而不是排序的 O(n log n)。

下标换算：升序排列后，「第 k 大」就是下标 len(nums) - k 上的元素。先把这个目标下标 target 算出来，之后一路只问「target 落在划分的哪一段」。

划分用三路划分（把区间分成 < pivot、== pivot、> pivot 三段，见排序），而不是两路：本题值域只有 [-1e4, 1e4] 而 n 可到 1e5，重复元素必然大量出现。两路划分遇到「全部元素相等」会把区间切成 1 和 n-1，每轮只缩短一格，退化成 1e5 * 1e5 / 2 = 5e9 次操作的 O(n^2)。三路划分把所有等于 pivot 的元素一次性归位，等值区间一轮就结束。

pivot 用三数取中（取区间首、中、尾三个值的中位数），不用随机数：教程仓库里的解法必须可复现，随机 pivot 每次跑出的比较次数都不一样，读者对不上账；而固定取端点（如永远取 a[hi]）在已排好序的输入上每轮只切掉一个元素，同样退化成 O(n^2)。三数取中是确定性的，对「已升序、已降序、前后两段有序」这些常见的坏输入都能给出接近中间的切分。

数据规模与复杂度¶

1 <= k <= nums.length <= 1e5，-1e4 <= nums[i] <= 1e4。期望时间 O(n)，额外空间 O(n)——为了不改动调用方的数组而复制了一份；循环写法本身不吃递归栈，所以没有 O(log n) 的栈开销。值域宽度只有 20001，也可以直接开桶计数做到 O(n + 值域)，但那依赖值域窄这个特殊条件，快速选择才是通用解法。

坑在哪¶

第 k 大对应的升序下标是 len(nums) - k，不是 k 或 k - 1。 k = 1（最大值）对应最后一个位置，k = n（最小值）对应下标 0。算成 k - 1 求出的是第 k 小，样例一会返回 2 而不是 5。
必须用三路划分。两路划分在全相等数据上（本题值域窄，很容易造出来）每轮只缩短一格，n = 1e5 时是 5e9 量级的操作，必然超时。三路划分把等值段整块跳过，全相等的输入一轮就结束。
不要用随机 pivot。随机能在概率意义上避开最坏情况，但本仓库是教程，每次运行的行为必须可复现。改用三数取中：确定性、对常见坏输入同样有效。若坚持取固定端点，已排好序的输入就会退化成 O(n^2)。
三路划分的三个指针含义要分清：lt 是「小于区的右开边界」， gt 是「大于区的左开边界」，i 是当前考察位置。遇到大于 pivot 的元素与 gt 交换后 i 不能前进——换过来的元素从未被检查过；遇到小于的与 lt 交换后 i 可以前进，因为 lt 处的元素必然是已检查过的等值元素（或就是 i 自己）。这与 LC75 荷兰国旗是同一套不变量。
循环终止条件不能漏 lo >= hi。区间收缩到只剩一个元素时它就是答案，不判这一条会在空区间上取三数取中而越界。
复制一份数组再动手。快速选择靠原地交换工作，直接在入参上做会打乱调用方的数组。本题只比对返回值，改了也不会被判错，但留下副作用不是好写法；代价是 O(n) 额外空间，愿意接受副作用的话可以省掉。
严格比对：第 k 大是一个确定的数值（按排序后的位置算，不是第 k 个不同的值），没有多解。样例二里 4 是第 4 大，重复的 5 各占一个名次。

样例复核¶

nums = [3, 2, 1, 5, 6, 4]，k = 2，n = 6，target = 6 - 2 = 4。第一轮 lo = 0, hi = 5：三数取中取 a[0]=3、a[2]=1、a[5]=4 的中位数 = 3。三路划分后数组变成 [2, 1, 3, 6, 4, 5]，等值区是下标 2..2，即 lt = gt = 2。 target = 4 > gt = 2，于是丢掉左段与等值区，只保留右段，lo = 3。第二轮 lo = 3, hi = 5：三数取中取 a[3]=6、a[4]=4、a[5]=5 的中位数 = 5。划分后数组变成 [2, 1, 3, 4, 5, 6]，等值区是下标 4..4，lt = gt = 4。 target = 4 落在 [lt, gt] 内，直接返回 a[4] = 5。返回 5，与题面一致。整个过程只碰了 6 + 3 = 9 个元素，比完整排序省下的正是「另一半不用递归」这部分工作。

参考实现¶

solutions/leetcode/LC215/sol.py
from typing import List, Optional


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 复制一份再原地交换：快速选择必须打乱元素位置，
        # 直接改入参会给调用方留下副作用。代价是 O(n) 额外空间
        a = list(nums)
        # 下标换算：升序排好后「第 k 大」落在下标 len(a) - k。
        # k = 1 对应最后一位，k = n 对应下标 0。写成 k - 1 求到的是第 k 小
        target = len(a) - k
        lo, hi = 0, len(a) - 1
        while True:
            # 区间只剩一个元素时它必然就是答案；不判这条会在空区间上取中位数而越界
            if lo >= hi:
                return a[lo]
            # 三数取中选 pivot：确定性、可复现，比随机 pivot 更适合教程；
            # 而固定取端点在已排好序的输入上每轮只切掉一格，会退化成 O(n^2)。
            # max(min(x, y), min(max(x, y), z)) 就是三个数的中位数
            mid = (lo + hi) // 2
            x, y, z = a[lo], a[mid], a[hi]
            pivot = max(min(x, y), min(max(x, y), z))
            # 三路划分，循环不变量（与 LC75 荷兰国旗同构）：
            #   a[lo : lt] < pivot，a[lt : i] == pivot，
            #   a[i : gt + 1] 未知，a[gt + 1 : hi + 1] > pivot
            # 用三路而不是两路，是因为本题值域只有 [-1e4, 1e4] 而 n 可到 1e5，
            # 重复元素极多；两路划分在全相等数据上每轮只缩一格，退化成 O(n^2)
            lt, i, gt = lo, lo, hi
            while i <= gt:
                if a[i] < pivot:
                    # 小于区扩张。lt 处原本是已检查过的等值元素（或就是 i 自己），
                    # 换过来的不必重看，i 可以安全前进
                    a[lt], a[i] = a[i], a[lt]
                    lt += 1
                    i += 1
                elif a[i] > pivot:
                    # 大于区扩张。gt 处的元素**从未被检查过**，
                    # 换过来的可能是任意值，所以 i 原地不动，下一轮重新判定
                    a[i], a[gt] = a[gt], a[i]
                    gt -= 1
                else:
                    # 等于 pivot，已经落在中段该在的位置，直接并入
                    i += 1
            # 划分完毕：[lt, gt] 这一段全部等于 pivot，且已经在最终位置上。
            # 只需判断 target 落在哪一段，另一段整个丢弃——
            # 这正是快速选择比快排省下一半工作的地方
            if target < lt:
                hi = lt - 1
            elif target > gt:
                lo = gt + 1
            else:
                return a[target]

LC215 数组中的第K个最大元素¶