刷题这东西总有几道题会隔三差五地跟你重逢。Day33我又撞上了LeetCode 215——数组中的第K个最大元素。实话讲这道题我在电话面里被问过在模拟面试里看别人写过还在某次 code review 里看到同事把线上的“Top K”需求直接 sort 了一把。题面一句话的事给定整数数组 nums 和整数 k返回数组中第 k 个最大的元素。但这句话背后至少藏了三套思路排序、快速选择、堆。三种解法对应三种复杂度模型也对应三种不同的应用场景。面试官爱问这道题恰恰是因为它能快速分辨一个人是背过答案还是真理解算法本身。这篇东西写给刚开始刷题的朋友也写给把答案背下来却还没想明白“为什么”的人。我会把三种解法完整过一遍补上复杂度推导再聊一个很多人踩过的重复元素坑最后说说这道题在工程里的真实用法。放心不绕弯子全是能直接拿去用的东西。1. 题面里藏着的两个关键点语义与数据规模1.1 “第K大”不等于“去重后的第K大”先解决最容易踩的语义坑。题目说的是“返回数组中第 k 个最大的元素”这里默认的是排序之后从大到小数第 k 个位置上的值。它不要求元素唯一所以重复值每一个都算数。举个例子。nums [3, 2, 1, 5, 5, 4]k 2。排序后是 [1, 2, 3, 4, 5, 5]从大到小数第二个是 5所以答案是 5。如果误把题目理解成去重后的第 2 大那答案就变成 4 了直接错。这个细节在面试里经常被用来做“试探性提问”。你如果一上来就写nums[nums.length - k]面试官会紧跟着问一句“那如果我要的是去重之后的第 K 大呢”这不是刁难而是想看你会不会主动意识到两个问题的处理差异。去重版本需要用哈希表或者排序后跳过相邻重复元素复杂度模型完全不一样。1.2 看一下约束再选策略刷题第一件事永远是看数据范围。LeetCode 215 的约束是1 ≤ k ≤ nums.length ≤ 10^5nums[i] 在 -10^4 到 10^4 之间。这个范围意味着最暴力的思路——直接排序——其实是能过的毕竟 10^5 个元素的排序在现代机器上就是毫秒级。但“能过”和“答得好”是两回事。面试官要的不是一个能 AC 的提交而是你能不能在 N 达到百万、千万甚至更大时依然给出一个可扩展的方案。这也是这道题存在的意义它把一个“看似简单”的问题拆成了一条鄙视链——排序法、堆法、快速选择法每个层级都能说明你对复杂度和场景的理解深浅。我把三种主流解法放在一起先看个全貌后面逐个展开。解法平均时间复杂度最坏时间复杂度空间复杂度核心优势全量排序O(N log N)O(N log N)O(1)满足库函数实现最简单快速选择O(N)O(N²)O(1)迭代版静态数组效率最高大小根堆O(N log K)O(N log K)O(K)天然适配数据流与海量数据这张表的含金量很高。面试时你能报出这张表基本就把这道题的主干知识讲完了剩下的都是细节。2. 排序法能过测试但赢不了面试2.1 三行代码的“满意解”先看最直白的写法。Java 里用Arrays.sortPython 里用内置sorted本质一样class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } }逻辑一句话升序排序后第 k 大的元素在正数下标nums.length - k的位置上。别把这个小写没写你页面你只需要知道一个结论升序数组里从右往左数第 k 个元素就是第 k 大。这道题的测试用例用排序法能直接过而且提交时间通常很好看。不少初学者刷到这就点“题解”了但我的建议是排序法只适合当开场白别把它当最终答案。2.2 复杂度账N log N 到底贵在哪排序的时间复杂度是 O(N log N)。当 N 10^5 时N log N 大概是 170 万次比较操作确实不算什么。但如果 N 涨到 10^7、10^8这个量级就开始肉痛了。更重要的是排序做了大量“多余”工作——它把整个数组排好了可你只关心第 k 个位置上的值。打个比方你参加一场考试想知道自己是第几名排序法是让所有人按分数重排一遍然后看第 k 个人是谁更聪明的做法是每次只淘汰一批明显不如你的人直到确定自己的位置。后者不用处理所有名次信息自然是更优解。还要注意一个细节Arrays.sort是原地排序意思是你的nums数组会被修改。如果业务代码里数组还要继续用你就得先拷贝一份空间和时间都会额外增加。这点在刷题时没人管但工程里经常被忽略。2.3 排序法的正确打开方式那排序法是不是就一无是处也不是。它有几种很合理的适用场景数组长度很小比如几百排序法的常数优势让复杂度的差别变得无所谓你只需要一次性查询且不关心原数组是否被改动作为面试答题的“第一层”先给一个能跑的版本再自然过渡到更优方案。我习惯这么面试先写排序法然后主动说“这个解法的时间复杂度是 O(N log N)但如果面试官希望更快我可以调整到平均 O(N)”。这套递进在面试官眼里是加分的因为它说明你不只会背题还有自己的复杂度判断能力。真正的问题来了能不能做到比 O(N log N) 更快答案是可以就看下一章。3. 快速选择每次砍掉一半平均 O(N)3.1 核心是 partition不是排序快速选择Quick Select的思路源自快速排序里的 partition 操作。partition 干的事是选一个基准值 pivot把数组划分成“小于 pivot”和“大于 pivot”两段然后返回 pivot 最终所在的位置。快排会递归地把左右两段都排好但快速选择只需要回答一个问题目标下标在左边的区间还是右边的区间每次划分后答案只可能存在于一边所以另一边的数据可以直接无视。这就是它能从 O(N log N) 降到 O(N) 的根本原因。把原始数组按升序理解第 k 大的元素在排序后数组的下标是n - k。我们把这个值叫targetIndex。每次 partition 返回的pivotIndex如果等于targetIndex那 pivot 就是答案如果小于它说明答案在右侧如果大于它说明答案在左侧。于是循环地把区间缩小直到找到为止。3.2 一个具体的推演过程拿个具体例子走一遍。nums [3, 2, 1, 5, 6, 4]k 2那么 n 6targetIndex 4。第一轮 partition 选 pivot 4刚好数组最右边那个。把小于 4 的换到前面大于 4 的留在后面同时把 4 放到它该在的位置得到 [3, 2, 1, 4, 6, 5]pivot 的下标是 3。因为 3 4说明答案不可能在下标 3 左边我们把搜索区间缩到 [4, 5]也就是子数组 [6, 5]。第二轮在这个子数组上 partition随机选到 pivot 6。交换后 6 到最右边5 被换到左边得到 [3, 2, 1, 4, 5, 6]pivot 的下标是 5。因为 5 4说明答案在左侧区间缩到 [4, 4]。第三轮区间只剩一个元素 5partition 返回下标 4正好等于 targetIndex答案就是 5。整个过程只做了三次 partition处理的数组长度依次是 6、2、1加起来不到两倍的数组长度因此平均 O(N) 不是玄学是一条可以手推的等比数列。3.3 随机 pivot 是必需品快速选择不稳定的唯一来源是 pivot 选得差。如果数组本来就有序而你又每次都选最右边那个元素当 pivot那每次 partition 都只会消掉一个元素复杂度退化成 O(N²)。这是“运气差”和“数据刚好克你”的双重作用。解法里必须有随机化。代码里我用Math.random()从当前区间随机选一个下标保证遇到有序数组、逆序数组这类刁钻输入时不至于每次都踩到最差 pivot。笔试时可能无所谓但工程里如果线上数据恰好有序固定选端点的写法可以直接把服务拖垮。这段是完整的快速选择实现迭代版本空间 O(1)class Solution { private int[] nums; public int findKthLargest(int[] nums, int k) { this.nums nums; int n nums.length; int targetIndex n - k; int left 0; int right n - 1; while (left right) { int pivotIndex partition(left, right); if (pivotIndex targetIndex) { return nums[pivotIndex]; } else if (pivotIndex targetIndex) { left pivotIndex 1; } else { right pivotIndex - 1; } } return -1; } private int partition(int left, int right) { int randomIndex left (int) (Math.random() * (right - left 1)); int pivot nums[randomIndex]; swap(randomIndex, right); int storeIndex left; for (int i left; i right; i) { if (nums[i] pivot) { swap(i, storeIndex); storeIndex; } } swap(storeIndex, right); return storeIndex; } private void swap(int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }这个版本可以直接提交。代码里有几个值得注意的点Math.random()虽然比ThreadLocalRandom慢一点但胜在零依赖、好理解storeIndex是经典的“读指针”和“写指针”分化的写法随机下标要算到right - left 1这个长度上别写成固定right。3.4 要不要上严格 O(N) 的算法面试时如果面试官继续追问“万一随机化还是遇到最坏情况呢”你可以提一个名字BFPRT 算法也叫 Median of Medians。它的思路是先把数组每五个元素一组找到每组的中位数再递归找这些中位数的中位数作为 pivot从而保证每次 partition 至少淘汰固定比例的数据把整体复杂度严格控制在 O(N)。但工程里几乎没人写 BFPRT。原因是常数因子太大了每五个一组的预处理、求中位数的递归、各种数组拷贝让它在实际运行中的性能甚至可能不如一个随机化快选。BFPRT 更多是理论意义属于“我知道它存在、能说出原理、但不会在生产代码里写它”的类型。能答到这里面试官的预期已经拉满了。4. 堆解法另一种复杂度模型另一种适用场景4.1 小根堆为什么能求出第K大第一次看到“求第 K 大却用最小堆”的人都会愣一下直觉是“求最大应该用最大堆”。但这道题恰巧是小根堆更合适。思路是这样的维护一个最多只有 k 个元素的小根堆堆顶永远是堆里最小的那个元素。每遍历一个新数如果当前堆没满直接入堆如果堆满了并且新数比堆顶更大那就弹出堆顶、把新数放进去。这等于堆里始终保存着“到目前为止最大的 k 个数”而其中最小的那个恰好就是第 k 大。用代码看更直观class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return minHeap.peek(); } }跑一遍 nums [3, 2, 1, 5, 6, 4]k 2。先放 3、2堆变成 [2, 3]1 比堆顶 2 小不换5 比堆顶 2 大弹出 2 放入 5堆变成 [3, 5]6 比堆顶 3 大弹出 3 放入 6堆变成 [5, 6]4 比堆顶 5 小不换。最后堆顶是 5正确。4.2 小根堆与大根堆的对比有人写堆解法时喜欢用大根堆把所有元素丢进大根堆然后做 k-1 次弹出堆顶就是答案。大根堆的思路完全对但有两个不划算的地方空间上要装下全部 N 个元素是 O(N)时间上每次入堆 O(log N)全部入堆就是 O(N log N)比小根堆的 O(N log K) 差一档。方案空间复杂度时间复杂度适用场景小根堆固定 K 大小O(K)O(N log K)数据流、海量数据、K 很小大根堆全量入堆O(N)O(N log N)思路直观但处处吃亏快速选择O(1)平均 O(N)一次性查询的静态数组这个表格值得截图保存。我见过不少同学在面试里写出大根堆版本面试官一般不会说错但会追问“空间能压到 O(K) 吗”本质就是考察这个对比。Java 里PriorityQueue默认是小根堆所以小根堆不需要传任何参数大根堆需要传Comparator.reverseOrder()。还有个细节new PriorityQueue(k)里的 k 是初始容量不是“最大容量”堆满后它会自动扩容。所以代码里必须靠size()判断来手动限制大小别指望构造参数替你固定住。4.3 选堆还是选快速选择如果你手头的场景是“一次性给出完整数组只查一次”快速选择是更优解因为平均 O(N) 且空间 O(1)。但如果数据是持续到来的比如一个几百路并发写入的日志系统你永远不知道下一秒会不会来一个更大的值快速选择就只能重新跑一遍而堆方案是增量式的——来一个处理一个始终维持 O(log K) 的单次成本。这也是为什么很多后台系统的实时排行榜模块底层是一个固定大小的堆而不是每隔几秒做一次全量排序。堆的结构决定它天然适合“流式更新”这是快速选择做不到的。再来一个量级上的感知N10^6K100堆的时间大约是 10^6 * log2(100) ≈ 700万次堆操作排序是 10^6 * log2(10^6) ≈ 2000万次比较。堆不一定碾压排序但当 K 远小于 N 时堆的常数和内存占用都更可控尤其 K 小得离谱时优势会放大。5. 重复元素专杀三路 partition 与退化防御5.1 同一个数字刷满数组会发生什么前面写的快速选择其实还有一个隐藏的天坑大量重复元素。考虑一个极端用例数组里全是同一个值比如 10^5 个 7k 2。基础版 partition 会选一个 7 当 pivot然后遍历数组时发现所有元素都不小于 7于是一个都没换最后把 pivot 换到storeIndex也就是区间开头的位置。结果每次 partition 只处理掉一个元素退化成 O(N²)。LeetCode 的测试用例里包含大量重复值的场景。我在本地用这个用例跑过基础版快选耗时惨不忍睹。这就是为什么实际刷题时很多答案会推荐用“三路 partition”来替代基础版本。5.2 荷兰国旗 partition 的写法三路 partition 的思想来自荷兰国旗问题将数组分成三块——小于 pivot、等于 pivot、大于 pivot。这样一大片等于 pivot 的元素在第一次 partition 后就能全部归位如果目标值正好落在这片区域里直接返回不需要再递归。具体实现private int[] partition3(int left, int right) { int pivot nums[left (int) (Math.random() * (right - left 1))]; int lt left; int i left; int gt right; while (i gt) { if (nums[i] pivot) { swap(i, lt); lt; i; } else if (nums[i] pivot) { swap(i, gt); gt--; } else { i; } } return new int[]{lt, gt}; // 等于 pivot 的区域是 [lt, gt] }主循环也要跟着改。不再只比较一下pivotIndex和targetIndex是否相等而是看targetIndex落在三区中的哪一区int[] range partition3(left, right); if (targetIndex range[0]) { right range[0] - 1; } else if (targetIndex range[1]) { left range[1] 1; } else { return nums[targetIndex]; }这段代码处理“全是同一个数”的用例时非常漂亮第一次 partition 就把整个数组划到等于区域targetIndex必然落在区域内直接返回。等于区域越大节省的时间越多。你可以把三路 partition 当成快选在生产环境中的默认形态。5.3 实测感受与实际提醒我在本地对比过两个版本随机数组时两者表现接近但以下两种情况三路版优势非常明显一是数组里存在大量重复值二是数组有序或逆序的“结构化”数据。后者靠随机 pivot 能化解一部分但重复值的问题只能靠三路 partition 根治。还有一个小提醒三路 partition 返回的是一个长度为 2 的数组代表等于 pivot 的范围。面试里单独写这个小函数能体现出你对快排底层的理解已经不是背代码的层次了。配合之前 BFPRT 的讲解这一整套快速选择相关的问题基本就问到顶了。如果你用 Java 写了三路版但提交超时先别急着怀疑算法。检查一下partition3里的Math.random()调用次数如果构造了大量小数组随机数生成的开销会被放大。这时可以把数组长度和 targetIndex 的关系单独处理比如当剩余区间小于某个阈值时直接排序返回工程上这叫“插入排序优化递归基”面试时提出来也是亮点。6. 从215题延伸出的Top K工程视野6.1 数据流里的实时第K大LeetCode 有一道题叫“数据流中的第 K 大元素”原题编号 703核心就是用一个固定大小的小根堆持续维护 Top K。你只要把 215 题的堆版本稍微封装一下加一个add()方法就是 703 题的完整解法。class KthLargest { private PriorityQueueInteger heap; private int k; public KthLargest(int k, int[] nums) { this.k k; this.heap new PriorityQueue(k); for (int num : nums) { add(num); } } public int add(int val) { if (heap.size() k) { heap.offer(val); } else if (val heap.peek()) { heap.poll(); heap.offer(val); } return heap.peek(); } }这道题在真实业务里的投影是“实时热度榜”短视频热度、直播间在线人数、搜索热词都是源源不断的数据流你不能把历史数据全存下来再一秒钟排序一次。小根堆方案可以做到每次新数据到达时只用 O(log K) 完成更新K 通常取 10 或 100成本完全可以接受。6.2 海量数据内存放不下时的应对如果数据量大到连单机内存都装不下比如 TB 级别的日志堆方案的 O(K) 空间优势就变成了决定性因素。因为你可以逐行读文件把每一行“喂”给一个固定大小的堆全程内存占用只有 O(K)跟数据总量无关。这是排序法在工程上的致命伤Arrays.sort需要把整个数组放进内存海量数据场景根本走不通。所以我在某后台服务里做过一个 Top 错误码统计模块就是拿一个 100 大小的小根堆配合哈希表先计数再逐条喂给堆。代码量不大却能稳定处理每天几十亿条上报。还有一种常见方案是“分桶归并”把海量数据按哈希分到多个小文件里分别求每个文件的 Top K最后再对所有 Top K 做一次归并排序。这种方式适合分布式环境每台机器只处理自己那部分数据最后汇总。它和“最小堆”并不冲突归并阶段用的还是堆。6.3 变体题与我的刷题体会215 题的变体一大堆但思路是复用的求第 K 小等价于求第 N-K 大直接套前 K 个高频元素先用哈希表统计频率再对频率做 Top K数组中最接近原点的 K 个点把距离算出来变成第 K 大/小问题数据流中位数两个堆一个大根堆一个小根堆是 215 题堆思路的进阶版。我自己刷这道题最大的收获不是记住了快速选择的代码而是建立了一种“复杂度模型”的直觉排序是万金油但很多问题根本不需要全序堆适合增量快选适合一次性当你发现一个题可以用两种复杂度模型解时一定要搞清楚场景再选那套合适的。如果只让我留一条建议给读者那就是三种解法都亲手写一遍然后不看题解在纸上把快速选择随机化后的复杂度推导写出来。这道题一旦吃透Top K 这个家族对你来说就算彻底通关了。