刷了这么多年的题Hot100 里能同时横跨“排序、堆、分治、快选”四个知识点的题其实不多215题“数组中的第 K 个最大元素”算是最典型的一道。不管你是准备国内大厂面试还是在系统设计里处理 TopN 问题这道题的几种解法几乎就是那套思路的微缩版——搞懂它等于把一堆看似高深的技巧打通了。这道题表面上只是问“返回排序后第 K 大的元素”但内里考的是你对“不需要全排序”的理解程度。很多人第一反应是直接排序能过但面试官大概率会追问一句“还有更好的做法吗”。所以今天我不光要把几种主流解法拆开揉碎讲清楚还会把快速选择的核心思想、堆的适用边界、边界条件排查这些实操经验一次说完。1. 题目本质与多解思路拆解1.1 先搞懂“第 K 大”到底在说什么原题描述很简单给定一个未排序的整数数组nums和一个整数k返回数组中第k个最大的元素。注意题目特别强调了“第 k 个最大的元素而不是第 k 个不同的元素”这句话意味着数组里的重复值要分开算。举个例子nums [3, 2, 1, 5, 6, 4]k 2升序排序后是[1, 2, 3, 4, 5, 6]第 2 大的元素是 5。但如果数组是[3, 3, 3, 1]k 2排序后是[1, 3, 3, 3]第 2 大是 3而不是“去重后的第二大”因为 3 出现了 3 次它占掉了第 1、2、3 三个位置。这里面有一个非常重要的索引换算关系一个长度为n的数组升序排序后第k大的元素就是降序排序后索引为k - 1的元素等价于升序排序后索引为n - k的元素。这个换算在快速选择算法里是核心中的核心搞错一位整个程序就废了。我习惯用一个生活场景来理解一个班 50 个人考试第 3 名是谁你先按分数从高到低排排第 3 个位置的就是。如果有两个人分数一样他们两个分别占第 2 名和第 3 名不存在“并列第 2 名然后下一个是第 3 名”这种说法——至少在这道题里不是。这样理解重复元素就不会出错。1.2 五种解法全景对比这道题我梳理下来至少有 5 条可以走通的路线每条路线的复杂度、代码量、适用场景都不一样。解法时间复杂度空间复杂度核心思想适用场景暴力排序O(n log n)O(1)全排序后取下标数据量小、代码最简快速选择Quick Select平均 O(n)最坏 O(n²)O(1)快排分区只搜一半面试重点考察、内存受限小顶堆维护 TopKO(n log k)O(k)堆里永远存最大的 k 个海量数据、流式数据大顶堆排序后取O(n log n)O(n) 或 O(1)全部入堆再弹出 k 次理解堆特性时用计数 / 桶排序O(n)O(max - min 1)值域有限时用空间换时间数据范围小、整数均匀分布这 5 条路线不是互相取代的关系而是不同场景下的不同取舍。暴力排序最简单但时间上不划算快速选择平均最快但最坏情况不稳定堆解法时间稳定、空间可控是工程里 TopK 问题的最优解计数排序只在值域受限时才能用。这些我会在后面的小节里逐个展开。2. 快速选择平均 O(n) 的核心算法2.1 从快排到快选只搜一半的进化快速选择算法的全称是 Quick Select它和快速排序Quick Sort师出同门核心都是分区函数partition。快速排序每次把数组分成左右两半然后递归处理两边快速选择就不一样了——每次分区之后pivot 已经落到了它最终该在的位置如果这个位置恰好就是我们要找的n - k位置那就直接返回如果不是只需要递归进入包含目标位置的那一边另一侧直接扔掉不管。正因为每次只需要处理一半的数据快速选择的期望时间复杂度才会从快排的 O(n log n) 降到 O(n)。你可以把它理解成一个查字典的过程你不需要把整本字典从头到尾都抄一遍才能找到某个字只需要根据偏旁和笔画判断它在前半本还是后半本然后继续翻就可以了。每一轮搜索范围减半总工作量就是 n n/2 n/4 ... 2n也就是 O(n)。这个思路在面试里极其加分因为它直观地体现了“利用已有排序信息”的能力。很多候选人能写出排序解法但一问到快选就卡住主要就是对分区函数不熟以及不会把“第 K 大”映射到数组索引。2.2 手把手实现快速选择这里我给出一个 C 的实现代码里注释写得很细尤其是索引换算和递归边界这两个容易翻车的地方。class Solution { public: int findKthLargest(vectorint nums, int k) { // 第 k 大的元素在升序数组中的索引是 n - k // 我们在 nums 数组中找最终位置为 n - k 的元素 int n nums.size(); int target n - k; int left 0, right n - 1; while (left right) { int pivotIndex partition(nums, left, right); if (pivotIndex target) { return nums[pivotIndex]; } else if (pivotIndex target) { left pivotIndex 1; // 目标在右半区 } else { right pivotIndex - 1; // 目标在左半区 } } return -1; } private: // 分区函数返回 pivot 元素的最终位置 // 分区后pivot 左边的元素都小于等于它右边的元素都大于等于它 int partition(vectorint nums, int left, int right) { // 随机选择 pivot避免极端情况退化 int randomIndex left rand() % (right - left 1); swap(nums[left], nums[randomIndex]); int pivot nums[left]; int i left 1; // i 指向第一个大于 pivot 的位置 int j right; // j 从右往左扫描 while (true) { while (i j nums[i] pivot) i; while (i j nums[j] pivot) j--; if (i j) break; swap(nums[i], nums[j]); } // 最后把 pivot 放到正确位置 swap(nums[left], nums[j]); return j; } };这段代码里有两个关键设计。第一个是随机选 pivot我用rand() % (right - left 1)把 pivot 的位置从左边界随机化到整个区间这样可以避免输入本身是有序数组时每次选最左边的元素导致分区严重失衡从而退化到 O(n²)。第二个是双指针相向扫描i从左往右找第一个大于 pivot 的元素j从右往左找第一个小于 pivot 的元素找到后交换最终j指向的位置就是 pivot 该待的位置。很多人在写这个partition的时候容易犯一个错把while (i j)写成while (i j)导致循环结束后j的位置不对。你可以在纸上模拟一下[3, 1, 2, 5, 4]这个数组left 0pivot 3自己推一遍就明白了。2.3 为什么平均是 O(n)期望复杂度图解式理解我一直觉得只记住“平均 O(n)”是不行的面试官随便深挖一下就能知道你是背的结论还是真懂。假设分区函数每次都能把数组大致分成两半那么第一轮扫描整个数组要 n 次比较第一轮结束后我们要找的目标只可能在其中的一半里所以第二轮只需要扫描 n/2 个元素第三轮 n/4……直到只剩 1 个元素。总比较次数 T(n) n n/2 n/4 n/8 ...这是一个等比数列当 n 趋于无穷大时收敛到 2n所以期望时间就是 O(n)。但问题是分区不可能真的每次都是完美的一半。最坏情况下每次分区只排除掉一个元素比如输入数组已经是有序的而我们每次选的 pivot 恰好是最小值或最大值那么 T(n) n (n-1) (n-2) ... 1 O(n²)。随机化 pivot 的作用就是把“最坏情况出现”的概率降到几乎为零数学上可以证明随机快选的期望复杂度仍然是 O(n)而且常数因子比堆排序要小。为什么常数因子重要因为在实际工程里数据的规模可能达到百万级或千万级就算复杂度都是 O(n)运行时间也可能相差一倍以上。快选在“原地操作、缓存友好、常数小”这三方面都表现优异这也是它成为 LeetCode 官方推荐解法之一的原因。2.4 快选写法里的三大坑第一个坑是索引换算。我在代码里把第 K 大映射为升序数组的n - k索引如果你在降序方向上思考那就是k - 1。一部分人习惯把数组按降序排然后找k - 1这也可以但要在partition里把大于号和小于号反过来而且很容易在中间某个地方漏改一个符号。我建议固定用升序思维第 K 大 n - k索引这个换算最简单也不容易出错。第二个坑是递归边界。我的示例代码用的迭代写法while (left right)循环体内每次都会收缩范围所以不会死循环。如果你写递归版本一定要在递归函数开头判断if (left right) return nums[left]否则当pivotIndex target时没退出或者区间已经只有一个元素时继续递归就会陷入无限递归导致栈溢出。第三个坑是对重复元素处理不当。如果数组里全是同一个值比如全部是 5第一次 partition 的结果是什么我告诉你j会直接扫到left的位置返回的j left。然后你判断target在哪里如果target 0直接返回 5如果target 0就向右搜索但此时右边全是 5最终也能正确返回。关键在于partition里的等于号要斟酌nums[i] pivot这一侧放等于最终分区后左边是小于等于 pivot 的右边是大于等于 pivot 的。这样对重复元素是安全的。注意写partition的时候切忌一边用另一边也用。标准双指针写法的精髓是左指针跳过小于等于 pivot 的元素右指针跳过大于等于 pivot 的元素两边都包含等于这样相等的元素会均匀分布到两侧不至于让某一边极端膨胀。3. 堆与排序两条稳定路线3.1 小顶堆维护 TopK为什么不是大顶堆堆解法在工程里的地位非常高尤其是在海量数据场景下。它的思路是维护一个大小为 k 的小顶堆遍历数组时如果堆还没满直接入堆如果堆满了且当前元素比堆顶大就弹出堆顶、插入当前元素。这样做的好处是堆里永远保存着当前已扫描元素中最大的 k 个而堆顶最小值就是这 k 个里的最小也就是整体第 k 大的元素。为什么不用大顶堆呢用大顶堆的话堆顶是最大值你没法判断一个新元素能不能进 TopK——除非你把所有元素都塞进去那堆的大小就变成 n 了空间复杂度变成 O(n)。小顶堆的精髓在于“淘汰制”新元素只跟当前第 k 大的值即堆顶比比它大才替换否则直接跳过。这就是“最小堆求最大 TopK、最大堆求最小 TopK”的由来。来一个 C 实现class Solution { public: int findKthLargest(vectorint nums, int k) { // 小顶堆堆顶是最小的元素 priority_queueint, vectorint, greaterint minHeap; for (int num : nums) { if (minHeap.size() k) { minHeap.push(num); } else if (num minHeap.top()) { minHeap.pop(); minHeap.push(num); } } return minHeap.top(); } };这个解法的时间复杂度是 O(n log k)空间复杂度是 O(k)。当 k 比 n 小很多时比如 n 100 万k 100log k 近似于一个很小的常数实际运行比快排还快。如果数组数据来自分布式系统或消息队列你根本没法一次性全排序这个时候小顶堆几乎是唯一解。3.2 排序解法能跑但别当唯一答案排序解法很简单先对整个数组升序排序然后返回nums[n - k]。代码三行class Solution: def findKthLargest(self, nums: List[int], k: int) - int: nums.sort() return nums[len(nums) - k]但这道题存在一个“逻辑陷阱”题目只要求找第 K 大的元素排序把所有元素都排好了做了很多无用功。面试时给出排序解法通常不会被挂但绝对拿不到加分。我会建议你把它当“保底答案”——如果面试官没有追问可以先说排序、再补一句“但我们可以用快速选择优化到 O(n)”这样反而显得你思路全面。另外排序解法有个隐形的额外好处如果你后续需要不止一个 TopK 元素比如既要第 K 大又要第 K 小那排序后的数组可以 O(1) 取任意位置的值。而快选和堆每次只能回答一个问题。3.3 JavaScript 里有哪些排序 API 可以配合使用前端同学刷这道题时Array.prototype.sort()是默认工具但它有一些坑需要注意。默认情况下sort()会把元素转成字符串再按字典序排序所以直接nums.sort()对数字数组是错的必须传比较函数// 升序排序 nums.sort((a, b) a - b); // 降序排序 nums.sort((a, b) b - a);如果你要自己实现快选JavaScript 版本和 C 的差异不大但要注意递归深度。当数组规模达到几十万、而且输入恰好是逆序或有序时递归快选可能触发调用栈溢出。这个时候要么改成迭代写法类似我前面给的 C 循环版要么在浏览器里用Array.sort()兜底——V8 引擎的排序底层是 TimSort对真实数据做了很多优化平均性能很好在最坏情况下也不会退化到 O(n²)。所以前端面试如果允许用内置排序直接排序然后取值是最稳妥的方案然后再引申“我们来讲讲更优的解法”。4. 进阶优化计数思想与真实系统里的 TopN4.1 计数 / 桶排序当值域有限时的 O(n) 解法有一个容易被忽视的隐藏分支如果数组里的元素值域很小比如分数 0-100、年龄 0-150或者是有限的字符串标签我们可以用计数排序/桶排序的思想把复杂度压到真正的 O(n)。思路是开一个足够大的计数数组count下标表示元素值count[i]表示值 i 出现的次数。然后从最大值向最小值累加计数直到累加和大于等于 k 时那个下标就是第 K 大的元素。这种方法的时间复杂度是 O(n maxVal)空间是 O(maxVal)当maxVal不太大时它是所有解法中最快的而且代码格外简单。举个例子nums [3, 2, 1, 5, 6, 4]值域 1-6开一个长度 7 的计数数组。扫描一遍得到 count[1]1, count[2]1, count[3]1, count[4]1, count[5]1, count[6]1。然后从 6 往下数累加计数值 6 出现 1 次计数为 1值 5 出现 1 次计数变成 2一旦计数 k假设 k2就返回当前值 5。注意负数的情况如果数组里有负数可以做一个偏移把最小值映射到 0。比如最小值为 -100那么原值i对应下标i 100。偏移之后计数数组的长度是maxVal - minVal 1空间可能比较大如果差值上百万这个方法就不行了。4.2 从刷题到工程TopN 问题在真实系统里的变形刷题刷到最后其实是在刷“抽象能力”。LeetCode 215 在真实系统里的直接对应物就是各种 TopN 场景。我给你列几个最常见的例子日志分析中从每天的千万条日志里找出错误数最多的 10 个服务实例。每台服务器实时维护一个小顶堆堆里存 top 10 错误数最后归并各台服务器的堆结果。电商大促大屏上显示销量最高的 20 个商品。数据是流式的每秒都有新订单不能全排序只能用大小为 20 的小顶堆实时更新。推荐系统需要从海量候选集里挑选得分最高的 1000 个结果。可以先粗排阶段用堆选 Top 1000再进入精排模型做二次排序。在这些场景里快速选择反而用得不多因为数据是持续到来的你不能等全量数据齐了再找第 K 大。小顶堆是流式 TopK 的标准答案而快速选择更适合“一次性数据全量已知但内存有限不能开堆/k 很大的情况”。理解每个方案在真实系统中的适用边界比单纯刷过 10 遍这道题更有价值。4.3 经典追问如果数据量太大无法全部载入内存怎么办这个追问几乎是算法面试的标配。我的思路是分治归并把数据切成若干份每份可以在内存里用快选或堆求出该份的 top k然后再对每个文件的 top k 做一次归并最终得到全局 top k。这样做的复杂度是“单机分片处理的复杂度 归并的复杂度”工程上完全可行。更进一步的方案是使用外排序External Sort它利用磁盘的连续读写能力先把数据分成多个有序文件再逐路归并。这种方案适合“必须拿到全排序结果”的场景但如果只需要 top k堆方案比外排序更高效——因为外排序把 k 之外的元素也排好了浪费了 IO。面试官如果问到这里一定要顺着“IO 是瓶颈”这个点来讲方案取舍。5. 常见问题与排查技巧实录5.1 边界条件k0 和 kn 怎么防御LeetCode 题目限定 k 在[1, nums.length]范围内所以正常刷题不用管。但真实面试中面试官喜欢加问“如果 k 是 0 或者比数组长度还大呢”如果你提前做了防御观感会好很多。快选解法里循环条件left right本身就隐含了如果范围非法就会退出不会死循环。堆解法里如果 k0priority_queue不能入堆top()会崩溃。我一般在代码开头加一行if (k 0 || k nums.size()) return -1;这是一个防御性编程的习惯实际项目里非常有价值。数组边界这种事出事就是线上 P0 事故多一行判断少一次不眠夜。5.2 快选最常见的 Bug分区后索引偏差我见过新手写快选partition返回的 pivot 位置和真正的最终位置差了 1结果在while里左右搜不到目标要么死循环要么返回错误值。这个问题90%出在你用的是“挖坑法分区”最后把 pivot 放回去的位置和你在主函数里判断的位置没有对齐。建议用一个极端简单的数组反复验证自己的 partition 逻辑。比如nums [1, 2]k1目标索引是2 - 1 1。你手动跑一遍代码看看 partition 第一次返回的是不是 1如果不是 1说明分区写法有问题。这种“小数组手推验证”的习惯比任何调试技巧都管用。5.3 堆解法超时的常见原因堆解法超时十有八九是堆的容量没有限制在 k。有的人思路是“全部入堆再弹出 k 次”当 n 100 万k 100 时全部入堆的时间是 O(n log n) 100万 * 20 2000万次操作虽然也不慢但比你只维护大小为 100 的堆100万 * log100 100万 * 7要多出接近 3 倍的时间。更大的问题是空间全部入堆需要 O(n) 内存如果数据大到一定级别直接内存溢出。另一个隐蔽问题是用大顶堆做这件事找第 K 大却用大顶堆维护前 k 个堆顶是最大值新元素永远小于堆顶也就永远不会替换最后返回的堆顶根本不是第 K 大而是最大值。这个错误方向一错结果就是错的还特别难察觉。记住口诀找最大的 K 个用最小堆找最小的 K 个用最大堆。5.4 手写 partition 时防止死循环的小技巧写双指针扫描的partition时很多人会遇到死循环。核心技巧在于两段内层while里的边界条件一定要带上i j同时把i的初始值设为left 1。如果你初始值设成left那么当nums[left]等于 pivot 时内层while可能立即停止外层进入死循环。另外如果你使用的是“挖坑法”写分区要注意最后把空的坑位填回 pivot 值时那个坑的下标和你计算的目标索引是否一致。两种分区法没有高下之分但千万不要在同一个程序里混着用两套思路那是 bug 的重要来源。6. 总结刷题之外的几点体会刷 Hot100 刷到第 215 题时我最大的感受是一道题引出的知识密度远超它本身的难度标签。快速选择让你理解“不需要全排序”的优化思维小顶堆让你理解流式 TopK 的工程套路计数桶排序让你理解“数据特征决定算法选型”这三层递进关系在真实项目里遇到 TopN 需求时几乎可以直接映射过去。我在实际刷题中的习惯是先手推一遍小数组的 partition 过程再动手写代码写完跑测试用例时故意构造几个极端输入——全递增、全递减、全相等、单个元素、两元素镜像用来验证边界条件。这道题用这组用例走一遍基本就把所有坑都踩完了。如果你把这道题吃透后面的 4. 寻找两个正序数组的中位数、23. 合并 K 个升序链表这些 Hot100 题目你会发现它们和 TopK 是同一个思想体系里的不同变体。把一道题打穿比低效刷十道题更有用。