LeetCode 215. 数组中的第 K 个最大元素：不排序，怎么选出第 k 名

「找出第 k 大」不是面试官发明的玩具题：热搜榜是实时的 Top K，监控告警里「耗时最高的 1% 请求」是 Top K，推荐系统的候选截断还是 Top K。这道题的妙处在于它精确地卡在两把尺子中间——排序一次是 O(n log n)，正确但没用到「只要一个名次」这个信息；逐个比较 O(n²)，笨到不用讨论。在「我只要第 k 名」和「我不想全排序」之间，站着两个优雅的答案：堆与快速选择。LeetCode 215 把这道题标为中等，但它的变体几乎统治了算法面试的后半场。

题面与约束

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

约束条件：1 <= k <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4。两条约束都有信息量。「不是第 k 个不同元素」意味着重复元素占名次：[3,2,3,1,2,4,5,5,6] 里第 4 大是 4，不是把去重后的第 4 名 2 算进来——读错这一句，解法直接全错。「值域有界」（两万个可能的取值）则埋了一条官方没说破的捷径：值域这么窄，计数排序一趟就能解决，后面会提。示例：[3,2,1,5,6,4]，k=2，答案是 5。

先把问题翻译一遍

第 k 大的元素，就是数组升序排序后下标为 n - k 的那个元素（n 是数组长度）。这个下标转换是后面快速选择版本的锚点：整个算法本质上是在「不完整地排序」——不断缩小目标下标所在的区间，直到它被一个元素命中为止。

解法一：大小为 k 的小顶堆

直觉上「找最大的 k 个」似乎该用大顶堆，但反过来想：用一个只装 k 个元素的小顶堆，堆顶就是这 k 个里的最小值——也就是当前的第 k 大候选。数组从头扫到尾：

• 堆不满 k 个：直接放入；
• 堆已满：当前元素比堆顶大，说明堆顶「退休」，换入当前元素（heapreplace 一步完成弹出与压入）；否则这个元素连前 k 都进不去，跳过。

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        heap: list[int] = []
        for x in nums:
            if len(heap) < k:
                heapq.heappush(heap, x)
            elif x > heap[0]:
                heapq.heapreplace(heap, x)
        return heap[0]

时间 O(n log k)：每个元素至多触发一次堆操作，堆的高度只有 log k。空间 O(k)。

补一句堆本身的结构账，因为「堆顶为什么永远是最小值」值得有一句话的答案。堆不是排好序的数组，而是一棵藏进数组里的完全二叉树：下标 i 的孩子是 2i+1 和 2i+2，整棵树只靠下标关系维系，不需要任何指针。它只维护一条局部纪律——父节点不大于任何孩子（小顶堆），这条纪律保证了全局最小值一定在根上，但左右孩子之间没有任何顺序承诺。heapreplace 做的事是把根弹掉、把最后一个叶子搬到根上、再让它沿着树往下换到合规的位置（sift-down），路径长度就是树高 log k。理解了这一点就明白：堆用「放弃全局有序」换来了「最值可查、插入删除对数级」——而 Top K 问题恰好只需要最值，不需要有序，两者严丝合缝。

它还有一个快选给不了的杀手锏：数组可以不用一次到货。数据流式地来、只维护一个 k 大小的堆，任何时刻被问到「当前 Top K」都能立即作答——生产系统里排行榜、滑动窗口 Top K 全是这么做的。这是堆解法在工程里比快选更常见的根本原因：真实世界的 Top K 是一个持续进行的状态，不是一次性计算。

解法二：快速选择——只递归一半的快排

快排的 partition 有一个被浪费的性质：一次划分之后，pivot 的最终位置就确定了，左边的元素都小于等于它，右边都大于等于它——不管左边内部怎么排，第 n-k 个位置上的答案如果恰好落在某一侧，另一侧就永远不用管了。快排要两半都递归，所以是 O(n log n)；快速选择只递归包含目标下标的那一半：

期望复杂度：n + n/2 + n/4 + ... = 2n = O(n)

每一轮期望把搜索区间砍半，求和是 2n。这就是题目 follow-up 要的线性复杂度——不排序，但借用排序的过程，且只走一条路径。

import random

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        nums = list(nums)                    # 不想动输入就先拷贝
        target = len(nums) - k               # 第 k 大 = 升序下标 n-k
        left, right = 0, len(nums) - 1
        while True:
            if left == right:
                return nums[left]
            pivot = nums[random.randint(left, right)]
            lt, i, gt = left, left, right    # 三路划分：[< pivot | == | >]
            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

这段代码里有两个必须讲清的防御工事。随机化 pivot：快选的平均复杂度成立的前提是 pivot 大致居中，如果固定取左端点，一个已经有序的数组会让每轮只砍掉一个元素——退化到 O(n²)。随机选一个，退化概率就被压到可以忽略（本文本地实测：10 万个元素的有序输入，随机化快选 0.021 秒）。三路划分：标准二路划分在「大量重复元素」上会二次翻车——全相同元素时每个 pivot 都几乎不缩小区间。三路划分把数组切成「小于 | 等于 | 大于」三段，等于 pivot 的一段整块出局，重复元素越多反而越快。本文用 20 万个全相同元素实测，快选瞬间返回。

while 循环为什么一定停在正确答案上？靠一个区间不变量：target 永远落在 [left, right] 之内，且该区间内的元素集合在每一轮之前后，恰好是「原数组里第 target 名之前那个位置所在区间」的正确候选。三路划分之后区间被切成三段：target 落在「小于」段就收缩右边界，落在「大于」段就收缩左边界，落在「等于」段则答案就是 pivot 本身——因为等于段的所有元素原封不动地占据着排序后它们该占的位置。区间每轮严格缩小、target 又始终在界内，left == right 或命中等于段时返回的值必然是排好序后 target 位置上的元素。这就是「不完整排序」的安全边界：我们没有排的部分，永远与答案无关。

两个复杂度数字的精确表述：快选的 O(n) 是期望复杂度，最坏仍是 O(n²)（存在理论上的确定性线性算法——1973 年 Blum、Floyd、Pratt、Rivest、Tarjan 五位图灵奖或知名学者的 median-of-medians 算法，最坏也是 O(n)，但常数太大，工程与竞赛里都用随机化版本）。空间上快选是原地的 O(1) 额外空间（迭代写法），堆是 O(k)。顺带一提递归版本的栈深度：期望 O(log n)，但最坏退化场景下会到 O(n)——上一篇文章里 10 万节点链状树打爆 Python 递归的教训在这里同样适用，正式实现建议用本文的迭代写法，循环加两个下标变量，栈深度风险直接归零。

本地实测：两条路的真实差距

口径说明：本文代码在本地（Python 3）实测，100 万个随机整数、取中位数名次（k = 50 万），两种解法与排序对拍一致。

快选快于堆，符合理论预期（2n 次比较对比 n log k 次），但注意它没有快出一个数量级——O(n log k) 与 2n 在 n = 10^6、k = 5×10^5 时相差的倍数只有约 2.2，再算上堆操作常数更小的因素，两者的现实差距远小于渐进记号的观感。这也提醒我们：渐进复杂度决定能不能做，常数决定好不好用，选型时两条都要看。

堆还是快选：一张决策表

还有一条题目约束赠送的隐藏路线：值域 [−10^4, 10^4] 总共两万个取值，开一个计数数组扫一遍，再从高到低累加计数到第 k 个，就是严格 O(n + V) 的计数排序解——没有递归、没有堆、退化分析都不需要。它是这道题约束条件的产物，换个值域就失效，恰好用来说明「先读约束再选算法」不是一句空话。

最后把视野拉到数据量再上一个数量级的场景：n 不是百万而是百亿——全站搜索词、全网点击流。这个规模下连 O(n) 扫一遍都太贵，精确 Top K 让位于近似方案：Count-Min Sketch 用少量哈希计数器以可控的误差率估算每个元素的出现频次，配合小顶堆维护候选，内存从「存下所有不同元素」降到常数级；Redis 的 ZSET（跳表 + 哈希）则是「中等规模、要求精确、更新频繁」场景的标准答案，热门榜单直接用 ZINCRBY 加 ZREVRANGE 维护。从本题的 O(n) 到流式的 O(k) 内存再到近似算法，Top K 展示了同一个问题如何随规模升级而改换整个算法生态——这也是它值得单开一篇的真正原因。

举一反三

Top K 一族的心法一句话：先问数据是一次到齐还是流式到达，再问要的是第 k 个还是前 k 个。前者的答案决定用堆还是快选，后者决定堆里装什么、怎么比。

参考资料

• LeetCode 215. Kth Largest Element in an Array：原题、约束与 O(n) follow-up。
• Blum, Floyd, Pratt, Rivest, Tarjan: Time Bounds for Selection（1973）：最坏线性时间选择的 median-of-medians 原始论文。
• Python heapq 文档：heappush / heapreplace 的语义与复杂度。
• doocs/leetcode：第 K 个最大元素多语言题解：社区维护的对照实现。