数组中的第K大元素：快速选择与堆排序解法精讲

第一次见这个题目是好几年前的事了。“215. 数组中的第K个最大元素”，看起来就是一道平平无奇的题，但后来我面试别人也好、自己刷题也好，发现它特别能看出一个人的基本功。很多人第一反应是排序，写上三行代码就跑通了，然后沾沾自喜；但也有不少人被追问一句“数据量很大怎么办”就愣住了。这篇文章想把这题真正讲透，从暴力解到快速选择、再到堆解法，每一步为什么这么做、复杂度为什么是这样、工程场景里应该选哪种，一次性说清楚。不管你是准备算法面试的开发者，还是日常写业务想处理TopK问题的工程师，看完都应该能直接上手。

1. 第K大到底是什么：先把定义和直觉搞明白

题目描述很简单：给定一个无序整数数组，找到数组中第K个最大的元素。注意是“第K大”，不是“第K小”，也不是“第K个不重复的最大”。这里的“第K大”有严格定义：把数组按降序排列后，下标为K-1的那个元素就是第K大。

举个例子，数组是 [3,2,1,5,6,4]，K=2。降序排列是 [6,5,4,3,2,1]，第2大就是5。这个定义看起来人畜无害，但实际写代码的时候有个很隐蔽的坑：很多人会先把数组从小到大排序，然后取 nums[n-k]，这边稍不留神就会把下标算错。

还有一个同样常见的坑是重复元素。比如数组是 [3,3,2,1,1]，问第3大是多少？降序排完是 [3,3,2,1,1]，第3大是2。注意这里两个3分别占了第1大和第2大的位置，而不是“去重后”的第3大。我在实际面试中见过不少候选人在这里纠结，他们会问“重复的算吗”，其实题目的意思就是原样计数，不去重。这一点先定下来，后面写分区、写堆才不会跑偏。

搞清楚了定义，再往深处想一步：这题到底想要考察什么？如果只追求“能过”，那排序确实够了。但排序把整个数组的完整顺序都算出来了，而我们只想要其中的某一个位置。这就有点像你只需要知道全班最高分是多少，却非要把全班所有同学的分数从低到高排一遍一样——事情是能办成，但干了很多没必要干的工作。所以这题真正的价值在于：“我不需要全局信息，我只想要局部信息的时候，能不能少做点事？”带着这个念头去看后面的方案，一切就顺理成章了。

2. 教科书解法：排序为什么能过但不香

先给出来最直接的方案，也算是很多人的第一反应：

python复制def findKthLargest(nums, k):
    nums.sort()
    return nums[-k]

如果是C++，就用 sort 然后取倒数第k个，逻辑一模一样。这代码没什么毛病，测试用例全都能过，LeetCode上甚至能拿个还不错的成绩。但你要是去面试，这么交上去之后，面试官大概率会追问一句：“还能不能更快？”

这时候你需要清楚地知道，sort 的时间复杂度是 O(n log n)。如果数组有一亿个元素，哪怕用C++写，这个排序的开销也非常可观。而且很多业务场景里，nums 可能是一个只读的数据源，你不一定允许原地修改数组；排序往往需要额外拷贝，空间上又是一笔账。

再往深里想，排序其实把信息算多了。假设K=1，也就是要找最大值，你只需要扫一遍数组，O(n)就完事了。但排序却要O(n log n)，做了大量无用功。K很小、K很大、甚至K在中间，排序的复杂度都是一样的，它完全没用到“K”这个参数带来的信息。

我自己当年刷这题的时候，也经历过“排序一把梭”的阶段，甚至觉得这题没什么意思。后来换了个思路：既然排序是把所有牌都翻开来理一遍，那能不能像打牌一样，我只关心牌堆里最大的那张牌或者前几大的那张牌，其他的牌看一眼就扔掉？于是就有了下面两种真正值得掌握的方案。

3. 快速选择：平均O(n)的分治方案

快速选择（QuickSelect）是这题最经典的进阶解法，思路和快速排序同源，但只处理快排中必要的一半，所以平均复杂度能做到O(n)。

3.1 核心思路：从快速排序里借用分治框架

快速排序的做法是选一个“主元（pivot）”，把数组分成两部分：比主元小的放一边，比主元大的放另一边，然后递归处理两边。快速选择借用了这个分区过程，但区别在于：每次分区之后，我会先判断目标元素落在哪一边，只递归进入那一边，另一侧直接扔掉。

这就好比你在一大堆试卷里找“分数第10高”的那张。你随手拿起一张当基准，让所有人按“分数高于它”和“分数低于它”分成两堆。数一下高分区有多少人：如果高分区正好有9个人，那基准这张就是第10高；如果高分区有20个人，说明第10高在高分区里，低分区整体都不要了；如果高分区只有3个人，说明第10高在低分区里，而且我要找的目标在低分区中其实变成了“第6高”（因为高分区已经有4个人挡在前面了）。每一轮都丢掉明显不可能是答案的那一堆，问题规模就迅速缩小了。

3.2 关键细节：第K大视角下的分区方式

写快速选择有一个很容易翻车的地方：分区方向。找“第K大”的时候，我把大于pivot的元素放左边，小于pivot的放右边，也就是降序方向排列。这样分区完成后，pivot所在的位置如果正好是第K大的位置，就直接返回；如果pivot的位置小于K-1，就去右边找；反之去左边找。

这个过程用代码表达更清楚：

python复制import random

def findKthLargest(nums, k):
    def quick_select(left, right, target):
        if left == right:
            return nums[left]

        # 随机选主元，避免最坏情况
        pivot_idx = random.randint(left, right)
        pivot = nums[pivot_idx]

        # 把主元先挪到最右边
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

        # 将所有大于 pivot 的元素往左边放
        store = left
        for i in range(left, right):
            if nums[i] > pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1

        # 主元放到正确位置
        nums[store], nums[right] = nums[right], nums[store]

        if store == target:
            return nums[store]
        elif store < target:
            return quick_select(store + 1, right, target)
        else:
            return quick_select(left, store - 1, target)

    return quick_select(0, len(nums) - 1, k - 1)

这里 target = k - 1 是因为下标从0开始，第K大在下标K-1。store 指向所有比 pivot 大的元素的下一个位置，最后交换之后 store 就是 pivot 在整个数组降序排列中应该待的位置。

3.3 为什么平均是O(n)而不是O(n log n)

这是很多人面试时被追问最多的地方。快速排序递归处理两侧，所以每层的总工作量是n，递归深度log n，总复杂度O(n log n)。而快速选择每次只进入一边，复杂度就变成了一个等比级数：第一次处理n个元素，第二次最多处理n/2个，第三次n/4个……加起来是 n + n/2 + n/4 + … ≈ 2n。所以期望复杂度是O(n)。

这个推导过程我当时第一次看到的时候觉得很惊艳，其实本质就是“每次扔掉一半，花在上面的时间不断减半”而已。类比一下就是：你要在一本1000页的字典里找一个词，正常人不会从第一页翻到最后一页，而是每次翻到中间，判断目标在前半本还是后半本，然后只继续翻那一半。

3.4 最坏情况与随机化救场

快速选择有一个最大的隐患：如果每次都选中当前区间里最大或最小的元素作为pivot，那么每次分区后只减少一个元素，复杂度直接退化到O(n²)。比如数组已经严格升序，而你又固定选最左边那个元素当pivot，那么每一轮处理一个超大区间，最后总的工作量就是n + (n-1) + (n-2) + … = O(n²)。

怎么解决？答案很简单——随机选pivot。虽然理论上仍然可能连续随机到最坏的主元，但概率极低，实际运行可以忽略不计。绝大多数工程实现都会用随机化来规避这个风险。也可以用“三数取中”之类的策略：取左、中、右三个位置的中位数当pivot，能进一步保证分区均衡。不过写面试题的时候，随机化就够用了，而且代码更简洁。

我在实际写代码时还踩过一个坑：主元交换的顺序。很多人手写快排时会用 while i < j 那种双指针模板，写完边界很容易出错。上面的写法，也就是开一个 store 指针从左往右扫把大于pivot的元素往前搬，最后再交换主元到 store 位置，是我觉得最不容易写错的版本，建议直接记这种。

4. 堆解法：内存受限和流式场景的答案

如果说快速选择是“离线全量数据”的王者，那堆解法就是“在线流式数据”的答案。后者在很多业务场景里甚至比前者更常用。

4.1 为什么用最小堆而不是最大堆

很多人听到“第K大”会下意识觉得要用最大堆：既然找最大，那当然用最大堆把最大的数堆出来。但仔细想想，如果你维护一个大根堆，最后能从堆顶拿到最大值，可题目要的是第K大，不是最大。你总不能把最大的弹出去再拿第二大的，弹K次。这样做在K很大的时候复杂度非常难看。

正确的姿势是维护一个“大小为K的最小堆”。什么意思？就是我始终保持堆里只有K个元素，而这K个元素是“到目前为止我见过的元素中最大的K个”。最小堆的堆顶是这个K个元素里最小的那个，也就是目前看到的“第K大”的门槛。每来一个新元素，就和堆顶比较：

• 如果新元素比堆顶还小，说明它连当前第K大都不如，直接跳过；
• 如果新元素比堆顶大，说明它有望进入前K大，于是把堆顶弹出，把新元素压进去，堆会自动调整。

这样遍历完整棵数组后，堆顶就是整个数组的第K大。

这个思想用生活化的方式说就是：你是一个选秀节目的导演，手里只有K个晋级名额。评委一个个把选手带进来，你手里始终保持最强的K个人。有人进来时，就和当前最弱的那位比一比，能赢就替换掉弱者，不能赢就淘汰。最终留在场上的虽然是最强的K个人，但你能直接看到的最弱一个，恰好就是第K名。

4.2 手推一个完整样例

用 [3,2,1,5,6,4]，K=2来走一遍：

最终堆顶是5，答案正确。

注意第四步和第五步，每次替换之后堆里始终只有K个元素，而且堆顶在持续变大。这个“门槛逐步抬高”的趋势就是整个算法的灵魂。如果你能把这个过程讲清楚，面试官基本能够确认你是真懂，而不是背了代码。

4.3 复杂度与实际代码

维护大小为K的堆，每次插入或替换都是O(log K)，总共处理n个元素，所以时间O(n log K)。空间上只需要O(K)，在海量数据但K很小的时候非常划算。

代码也很短：

python复制import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap[0]

Python里 heapq 默认就是最小堆。heapreplace 这个函数要注意一下：它是先弹出堆顶元素，再把新元素压入，比“先push再pop”效率高一些。如果你用的语言没有直接对应的操作（比如Java），可以先 poll() 再 offer()，效果一样。

4.4 堆的巨大优势：天然支持流式数据

堆解法最大的优势不在静态数组上，而在“数据源源不断进来”的场景。比如实时日志里统计当前访问量最高的K个IP、电商大促时实时维护销量前100的商品、推荐系统中维护用户最近最感兴趣的K个标签，这些都是源源不断有数据进来的场景。快速选择需要一次性拿到全部数据，而且会修改原数组的顺序，根本没法处理这种情况；而堆方案只需要维护K个元素，来一条处理一条，非常适合流式环境。

5. 两种方案到底怎么选：全方位对比

前面讲完了两种核心解法，现在把它们摆到台面上做一个系统对比，方便你在实际场景里做决策。

从表格能看出来一个关键结论：如果是一次性给全的静态数组，追求理论最优复杂度，无脑选快速选择；如果是动态数据流，或者你不能修改原数组，又或者内存非常有限，堆是更稳妥的选择。

还有一个容易被忽略的点：常数因子。快速选择在实际运行中虽然平均O(n)，但它的分区过程中有大量元素交换，常数因子并不小；而堆解法把时间复杂度放在每次log K上，在K比较小的时候实际跑起来非常快。如果你的场景是“一亿个元素找第10大”，堆解法往往在工程上是更接地气的选择。

面试的时候如果被问到“你会怎么选”，我的习惯是先反问几个问题：数据是一次性给全还是不断流入？数组允许原地修改吗？内存有没有限制？把这三个问题问完再选方案，基本就不会错。

6. 边界情况、重复元素与真实业务扩展

6.1 边界情况不能漏

算法题写对了主逻辑还不够，边界条件一定要考虑清楚。

• K大于数组长度：题目通常保证K有效，但工程代码里必须校验。
• 空数组或K小于等于0：直接抛异常或返回特定值，千万不要让代码在空数组上取下标。
• 数组只有一个元素：快速选择函数里的 left == right 条件就是为这种情况兜底的。
• 全相等元素，例如 [5,5,5,5]，K=2。快速选择里pivot选到5时，所有元素都不大于pivot，分区结束后store会在最左边，这时如果target不等于store，就只递归一边，依然能正确返回5。堆解法更简单，所有元素都不大于堆顶5，堆底不会替换，最终堆顶也是5。

在实际工程中，我见过太多线上事故不是主逻辑崩的，而是没处理K越界导致的。这个问题在刷题时不会暴露，因为平台保证了输入合法性，但换到真实业务里，输入从来不会按题目约定来。

6.2 重复元素为什么不会搞乱答案

有些人不放心：快排在处理重复元素的时候，等于pivot的元素到底放左边还是右边？其实都不影响最终正确性。因为我们的目标是“第K大”，不是“第K个不重复的最大”，也没有要求“稳定”或者“保留原始相对顺序”。等于pivot的元素无论被分到哪边，只要分区逻辑是确定的，最终pivot的位置就是它在降序数组里正确的位置，递归下去拿到的答案依然正确。

如果你用的是上面的代码，等于pivot的元素不会被搬到左边，因为判断条件是 nums[i] > pivot。这意味着所有等于pivot的元素最终都在pivot的右侧。这个分布是自洽的，不会影响结果。

6.3 从题目到业务：TopK类问题的泛化应用

把这道题吃透之后，你会发现它在业务里的应用远不止“数组找第K大”。我给你列几个我实际遇到过的场景：

第一，实时排行榜。某个活动页要展示实时销量前50的商品，数据一条条进来，不可能每次都全量排序。维护一个容量为50的最小堆，每次更新商品销量后就检查是否入堆，响应非常快。

第二，日志分析。线上服务每隔一段时间就要统计错误码出现次数最多的前10种。日志是流式的，而且基数可能非常大，堆解法完全适用。

第三，推荐系统粗排。当候选集特别大、精排模型跑不过来时，先用堆或者快速选择从几万条候选里捞出一小撮“看起来最有潜力的”，再送进精排。这一步本质上就是在做TopK。

实际上，我后来做大数据量统计时还会用到更进阶的近似算法，比如在内存里维护一定数量的随机样本，再基于样本估算全局TopK，或者用Count-Min Sketch这类概率结构来处理极高基数的流式数据。但无论这些方法怎么变，最基础的思想还是先想清楚：你要的是全局精确TopK，还是流式近似TopK？数据规模推高了什么瓶颈？这两个问题想通了，技术选型自然就有答案。

7. 刷题与面试中的几个实用心得

最后说点实操层面的心得，都是我自己实际踩过的坑。

第一，快速选择一定要随机选pivot。这个前面说过，但忍不住再强调一次。我在本地测试的时候用过“固定选最左边元素”的版本，测试数据一换成基本有序的大数组，运行时间瞬间飙升，跟排序没什么区别。后来改成随机化，才真正体会到O(n)的威力。

第二，堆解法注意“替换”和“先插再弹”的区别。如果你用 push 再 pop，堆的容量会短暂变成K+1，需要再写一行 pop，而且这样会多做一次堆调整。用 heapreplace 或者先 pop 再 push，每次操作只调整一次堆，效率更高。数据量大时这个差异是能感知到的。

第三，面试时别急着写代码。我见过很多候选人一上来就闷头写，写完发现方向错了。这题标准流程应该是：先确认要不要去重、数组可不可变、数据是一次性还是流式，然后基于这些约束给方案。哪怕最后选了最快的方法，你把约束条件讲清楚，面试官也会觉得你有工程意识。

第四，练这题的时候，建议把三种解法都写一遍，再手动跑几个例子。尤其是快速选择，你拿笔在纸上把分区的每一步画出来，比反复看十篇文章都有用。我那时候就是拿 [3,2,1,5,6,4] 手推了三遍，才把 store 指针的交换逻辑彻底记住。

最后一句话总结我的感受：很多人觉得这题考的是算法，其实考的是“信息判断”——你能不能判断哪些信息是必要的、哪些信息可以果断扔掉。排序拿到了全部信息，代价也高；快速选择和堆都是只拿必要信息，所以更快。想通了这一点，TopK这一类题都不会再难倒你。