力扣hot100里的第215题“数组中的第K个最大元素”我前前后后刷了三遍每遍的解法都不一样。第一次是排序一把梭第二次学了堆觉得“诶这题还能这么做”第三次研究明白快速选择才意识到这一道题背后其实串起了面试里最高频的几类算法思维。这篇文章就把我的完整实操过程拆给你看从最朴素的排序讲到工程里更常用的堆再讲到理论上更优的快速选择顺便把容易踩的坑都列出来。不管你是刚开始刷题的校招选手还是准备跳槽想突击热题的老兵这题都值得花时间吃透。1. 题目到底在考什么从一道题看三类核心解法1.1 题目描述与本质分析先看原题给定整数数组nums和整数k请返回数组中第k个最大的元素。注意要求的是“第 k 个最大元素”不是“第 k 个不同的最大元素”。举例来说nums [3,2,1,5,6,4]k 2返回5nums [3,2,3,1,2,4,5,5,6]k 4返回4。第一次看这题的人最容易懵的地方是“第 k 大”和“升序排序后第几个位置”的换算。如果数组按非递减排序第k个最大元素其实对应着下标n - k的位置其中n是数组长度。这个换算关系别搞反了我见过很多人在这个点上栽跟头代码逻辑写得挺对结果一换算就取错下标。这题考察的本质是“如何在未排序集合中找到第 K 大的值”。最简单的思路当然是排序但面试官往往不会满足于O(n log n)的解法。他们会追问能不能更高效如果数组大到内存放不下怎么办这正是这题的价值——它像一扇门推开之后就是堆、快速选择、分治这几类高频算法思维。1.2 解法全景图为什么这题适合反复刷我把这题的核心解法整理成了一张表大家先有个全局概念后面再逐个展开解法时间复杂度空间复杂度适用场景备注排序法O(n log n)O(1)数组完全在内存中最简单面试先说这个当基线小顶堆O(n log k)O(k)海量数据、流式数据工程最常用的思路快速选择平均 O(n)最坏 O(n^2)O(log n)递归栈数组完全在内存中理论上最优面试加分项nth_element平均 O(n)O(1)C 场景STL 直接提供内部就是快选思路刷题的时候建议按照这个顺序去理解先会写排序再学会堆优化最后理解快速选择。每往前走一步都能对“时间复杂度和空间复杂度怎么权衡”有更具体的体感。我第一次刷这题就是直接sort完事后来看题解才知道有这么多门道。2. 先写最朴素的排序解法理解代价才能超越2.1 排序解法的实现与复杂度排序解法没什么技术含量但它是理解后续优化的基石。核心思路把数组排好序然后按下标取第k个最大元素。写成代码非常简单// C 解法 class Solution { public: int findKthLargest(vectorint nums, int k) { sort(nums.begin(), nums.end(), greaterint()); return nums[k - 1]; } };# Python 解法 class Solution: def findKthLargest(self, nums: List[int], k: int) - int: nums.sort(reverseTrue) return nums[k - 1]// Java 解法 class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } }在 Python 里尤其要注意sort()和sorted()的区别。nums.sort(reverseTrue)是原地排序直接修改了nums而sorted(nums, reverseTrue)会返回一个新列表原来的nums不变。刷题和工程里如果写错了后面再使用nums就可能出现隐蔽的 bug。时间复杂度方面主流排序算法平均是O(n log n)空间复杂度看具体实现。C 的sort一般是内省排序空间复杂度接近O(log n)Python 的 TimSort 在最好情况下接近O(n)。对普通面试来说说“排序解法是 O(n log n)”就够了。2.2 排序方案值不值得写几个实际考量虽然排序是最“笨”的办法但实际开发里它反而经常是最稳的选择。为什么因为现代标准库的排序性能已经很恐怖了而且不需要你维护额外的数据结构代码不容易写错。我自己在真实项目里处理“取 Top K”需求时如果数据量在百万级以内、内存充裕很多时候就直接排序取前 K 个。不过在面试场景下排序解法只适合当“基线方案”。面试官如果继续问“能不能比 O(n log n) 更快”这时候就不能停在排序上了。要顺着这个提问把思路引到堆和快速选择上去。面试官想看的不是你会不会用sort而是你有没有考虑过“只关心第 K 个元素其实不需要全排序”这个点。还有一个实际问题如果数组必须保持原样不能修改排序解法需要先拷贝一份数组这会额外增加 O(n) 的空间代码虽然没变化但面试时要主动提到这个 trade-off。如果允许修改原数组堆和快速选择其实也需要修改原数组所以这个前提同样适用。3. 堆解法工程里真正常用的 Top K 方案3.1 为什么是“大小为 K 的小顶堆”很多人一听“第 K 大”就下意识想用大顶堆这是个经典的误区。如果维护一个大顶堆堆顶确实是最大值但每次弹出最大值后你得弹 K 次才能得到第 K 大复杂度反而变成了 O(n k log n)。当 k 接近 n 的时候这比排序还慢。更聪明的做法是维护一个大小固定为 K 的小顶堆。堆里保存的是“当前遍历过的所有元素中最大的 K 个”。因为是小顶堆堆顶就是这 K 个最大元素里最小的那个也就是当前的“第 K 大”候选。遍历数组时如果当前元素比堆顶大就把堆顶替换掉然后重新调整堆。遍历结束堆顶就是整个数组里的第 K 大。用一个生活化的比喻这就好比一个擂台赛台上永远只留 K 个最强选手新人来了如果比台上最弱的强就把最弱的踢下去。比赛结束后台上最弱的那位就是全场第 K 强。复杂度上堆的每次插入和弹出都是 O(log K)总共 n 个元素因此是 O(n log K)。重点是当 K 远小于 n 时这个算法的时间复杂度几乎可以看成 O(n)而且空间只有 O(K)。3.2 堆解法的代码实现三种语言对照下面是常用的堆写法我用三种语言都贴一遍方便大家对比。注意 C 和 Java 的默认堆是大顶堆需要额外指定成小顶堆Python 的heapq默认就是小顶堆反而最方便。// 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(); } };# Python 使用 heapq import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) - int: # 先用前 k 个元素建堆 heap nums[:k] heapq.heapify(heap) # 剩余元素逐个判断 for num in nums[k:]: if num heap[0]: heapq.heapreplace(heap, num) return heap[0]// Java 使用小顶堆 class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueueInteger minHeap new PriorityQueue(); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return minHeap.peek(); } }这里面有一个细节值得单独提一下heapq.heapreplace(heap, num)和heappushpop的区别。heapreplace是“先弹出堆顶再压入新元素”适合“新元素确定比堆顶大”的场景heappushpop是“先压入新元素再弹出最小值”适合不确定是否需要替换的场景。在这题里用heapreplace会稍微快一点因为省去了一次不必要的压入。3.3 堆解法在海量数据场景下的扩展价值堆解法最迷人的地方在于它天然支持数据流。如果数组大到内存根本放不下比如几亿条日志、几十 TB 的用户行为数据你不需要把所有数据读进内存。你可以一条一条地读取堆里只保存 K 个元素内存占用最多就是 O(K)。这也是为什么很多真实系统里统计“Top K”都用堆。比如我们要统计一个超大日志文件里访问频率前 10 的 IP伪代码思路就是# 海量数据 流式统计 Top K 的伪代码 import heapq from collections import Counter top_k [] counter Counter() with open(access.log, r, encodingutf-8) as f: for line in f: ip line.split()[0] counter[ip] 1 # 这里的 counter 数据量如果仍然很大就无法单机处理 # 进一步优化是滑动窗口 堆或者精确 Top K 用分段统计如果连每个 key 的计数都存不下那就需要 MapReduce 或者外部排序的思路先局部统计再全局合并。但无论怎么扩展堆在这个体系里都扮演着“保持 Top K 候选集”的核心角色这也是力扣这道题在工程面试题里地位高的原因。堆解法的另一个变体是求第 K 小。反过来想如果要找第 K 小就维护一个大小为 K 的大顶堆堆顶就是当前第 K 小的值。套路完全一样只是堆的方向反一下。我面试时被问到过变体题就是用这个思路答的。4. 快速选择面试官最想看到的进阶解法4.1 快排的思想怎么迁移到“找第 K 大”快速排序大家都知道选一个 pivot把数组分成左边小于等于 pivot、右边大于等于 pivot 的两部分然后递归排序左右两边。快速选择Quick Select利用了同一个 partition 过程但只处理我们关心的那一侧。具体的迁移逻辑如下。写一个 partition 函数它会把数组某个区间[l, r]内的元素根据 pivot 分成两部分并返回 pivot 最终所在的下标cur。此时cur位置的元素在整个数组中已经排到了它最终该在的位置。如果cur target说明第 K 大元素已经找到如果cur target说明答案在右侧区间如果cur target说明答案在左侧区间。无论哪种情况我们只需要递归或迭代处理一边。这个思路可以类比成查字典排序法是“从第一页翻到最后一页”而快速选择是“根据当前页的位置直接翻到左半本或右半本继续找”。每一轮缩小区间期望下只需要处理大约 n / 2、n / 4、n / 8……的元素总和收敛在 2n 左右所以平均复杂度是 O(n)。4.2 快速选择的代码实现Python/C/Java我用迭代写法实现快速选择避免递归深度过大带来的栈风险。这里选 pivot 的简单方案是取区间的最后一个元素同时注释里会说明如何随机化 pivot。# Python 快速选择 from typing import List import random class Solution: def findKthLargest(self, nums: List[int], k: int) - int: def partition(l: int, r: int) - int: # 随机选择 pivot 并交换到末尾避免最坏情况 pivot_idx random.randint(l, r) nums[pivot_idx], nums[r] nums[r], nums[pivot_idx] pivot nums[r] i l # i 左侧都是 pivot 的元素 for j in range(l, r): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[r] nums[r], nums[i] return i n len(nums) target n - k l, r 0, n - 1 while l r: cur partition(l, r) if cur target: return nums[cur] elif cur target: l cur 1 else: r cur - 1 return -1// C 快速选择 class Solution { public: int findKthLargest(vectorint nums, int k) { int n nums.size(); int target n - k; int l 0, r n - 1; while (l r) { int cur partition(nums, l, r); if (cur target) { return nums[cur]; } else if (cur target) { l cur 1; } else { r cur - 1; } } return -1; } private: int partition(vectorint nums, int l, int r) { int pivot nums[r]; int i l; for (int j l; j r; j) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; } } swap(nums[i], nums[r]); return i; } };// Java 快速选择 class Solution { public int findKthLargest(int[] nums, int k) { int n nums.length; int target n - k; int l 0, r n - 1; while (l r) { int cur partition(nums, l, r); if (cur target) { return nums[cur]; } else if (cur target) { l cur 1; } else { r cur - 1; } } return -1; } private int partition(int[] nums, int l, int r) { int pivot nums[r]; int i l; for (int j l; j r; j) { if (nums[j] pivot) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; i; } } int tmp nums[i]; nums[i] nums[r]; nums[r] tmp; return i; } }这个 partition 写法里有个细节循环条件是nums[j] pivot而不是。因为第 K 大允许重复元素并且我们需要让等于 pivot 的元素也集中在左侧这样数组才能被正确分割。如果写成遇到大量重复元素时partition 会把相等的元素全扔到右边导致区间划分极不均匀退化得很快。4.3 为什么平均复杂度是 O(n)“别被 O(n log n) 骗了”不少人第一次接触快速选择的平均 O(n) 时觉得很反直觉排序都要 O(n log n)凭什么找第 K 大能线形关键区别在于排序需要同时处理左右两侧的所有元素而快速选择每一轮只处理当前包含答案的那一侧。我来算一笔期望账。假设 partition 每次都能把数组大致对半分于是第一轮处理 n 个元素第二轮处理大约 n/2 个元素第三轮大约 n/4 个元素。总工作量是n n/2 n/4 n/8 ... ≈ 2n也就是说这个等比级数收敛到常数倍数的 n所以期望复杂度是 O(n)。这比排序的 O(n log n) 要低一个量级是“只解决部分问题”带来的收益。不过这里必须强调“期望”。如果 pivot 选得不好比如每次选到当前区间的最小值那么每一轮只能排除一个元素工作量变成n (n-1) (n-2) ... O(n^2)直接退化。这也是为什么要随机化 pivot 或者用三数取中法目的就是避免在已经有序的数组上出现这种灾难。面试的时候主动提一句“选择随机 pivot 是为了规避最坏情况”会显得你真的理解了这个解法的软肋。4.4 工程上对快速选择的几种优化手法快速选择虽然理论漂亮但工程上有很多细节能优化。我把自己常用的几个手段列出来第一三数取中法选 pivot。每次取nums[l]、nums[(lr)//2]、nums[r]三个数然后选其中位数作为 pivot。这个办法不需要随机数生成器在面对有序数组等极端输入时也很稳定。第二双路 partition / 三路 partition。当数组里有大量重复元素时标准的单路 partition 容易把相等的元素全部堆到一边导致递归退化成 O(n^2)。三路 partition 把数组分成“小于 pivot / 等于 pivot / 大于 pivot”三段等于 pivot 的区间可以直接跳过这样重复元素越多性能反而越好。力扣这题如果想冲击最优解三路 partition 是值得写的。第三递归转迭代。快速选择本质上每轮只处理一侧所以完全可以把递归改成while循环省掉递归栈的空间。我上面贴的代码就是迭代版本空间复杂度只剩 O(1)这在追求极致空间时很关键。第四C 直接用nth_element。STL 的algorithm里自带一个nth_element底层就是快速选择的优化实现可以这样用class Solution { public: int findKthLargest(vectorint nums, int k) { nth_element(nums.begin(), nums.begin() nums.size() - k, nums.end()); return nums[nums.size() - k]; } };这行代码在 LeetCode 上往往能跑出不错的时间因为它是库函数级别的优化。做笔试、打比赛的时候直接调 STL 是最划算的但如果面试官手写快速选择那就得老老实实把 partition 写出来。5. 常见问题与排查技巧实录5.1 边界条件与典型错误我踩过的坑我把这题和同类题里容易出问题的地方整理成了一份速查表都是我实际踩过坑之后记下来的问题具体表现原因与解决办法下标换算错误按升序排序后返回nums[k-1]升序数组里第 K 大元素对应下标n-k不是k-1混淆“第 K 大”和“第 K 大重复”[1,2,2,3]中误以为第 2 大是 2题目要求的是排序后第 K 个位置的值重复值也要算快速选择死循环while (l r)时 partition 始终无法收敛一定要用while (l r)且 partition 返回值要合理处理堆的方向选错用大顶堆求第 K 大第 K 大要小顶堆堆里保留最大的 K 个Pythonsort与sorted混用原地排序副作用导致后续逻辑错误如果函数内不想改原数组就显式拷贝k 超出范围k len(nums)时越界LeetCode 保证1 k n但面试变体题里要主动处理5.2 多语言排序 API 与数组初始化细节这个题目相关的热词里有很多是关于语言 API 的比如“js数组排序的几种方法”“数组初始化”“C 多维数组指针”等。我在这简单补充一段。JavaScript 里数组排序必须显式传比较函数因为默认是按字符串字典序排序的nums.sort((a, b) a - b)是升序nums.sort((a, b) b - a)是降序。很多 JavaScript 新手直接nums.sort()然后取第 K 个在个位数元素上能过遇到两位数的[100, 9, 2]就翻车了因为默认排序会得到[100, 2, 9]。C 的数组初始化方式也经常被问到。比如vectorint nums {3, 2, 1};固定大小数组int nums[10] {};会全 0 初始化二维数组vectorvectorint matrix(m, vectorint(n, 0));这种写法要熟记。真正写这题时我建议直接用vectorint因为它知道自己的长度不需要额外传 size 参数避免指针退化的问题。Java 里对int[]排序用Arrays.sort(nums)底层是快排的优化版本对对象数组排序用Arrays.sort()走归并排序稳定但空间占用更高。如果你在用 Java 写这题Arrays.sort(nums)之后取nums[n-k]是最快的方式。5.3 多语言实现对比速查表我把三种解法和三种语言组合成下面这张速查表写的时候方便对照也可以当复习材料语言排序解法堆解法快速选择解法备注Csort 取下标priority_queueint, vectorint, greaterint手写 partition 或nth_elementnth_element最省事Pythonnums.sort(reverseTrue)heapq.heapify heapreplace手写 partition 随机 pivotheapq默认小顶堆JavaArrays.sort 取下标PriorityQueueInteger默认小顶堆手写 partitionPriorityQueue默认是自然序小顶堆见过不少人在现场写 Java 的PriorityQueue时把poll()和peek()弄混。peek()只是查看堆顶不弹出poll()是弹出并返回堆顶。替换堆顶元素应该先poll()再offer()或者直接用heapreplace思路也行的 API。忘了哪个是哪个代码就会随机丢元素结果当然不对。6. 从“第 K 大”延伸到整个 Top K 家族6.1 这题能牵出哪些高频变体题把“数组中的第 K 个最大元素”吃透之后你会发现很多力扣热题都是它的近亲。比如力扣 347 “前 K 个高频元素”思路是先用哈希表统计频次再把频次数组当成一个“新数组”求该数组的第 K 大或 Top K力扣 692 “前 K 个高频单词”则在上一题基础上增加了字典序排序规则属于堆 比较器的综合题力扣 973 “最接近原点的 K 个点”则把比较规则换成了欧几里得距离。再往上拔一层面试里还有“海量数据找 Top K”这类系统设计题。数据不能全放内存时堆依然是最强的武器因为它只需要 O(K) 的空间就能在数据流中维护 Top K。如果单机都放不下 K 个元素那就用“分桶 各桶局部 Top K 合并全局 Top K”这已经进入外部排序和 MapReduce 的讨论范围了。6.2 我的刷题与工程实操体会回到开头那句话这题我刷了三遍每一遍都有新收获。第一遍我只会sort觉得题目太水第二遍用小顶堆体会到了“工程解法”的优雅第三遍认认真真推了几次 partition 和复杂度才明白所谓 O(n) 的快速选择是怎么回事。从实战的角度说一句掏心窝的话刷题归刷题真正到了生产环境写“取 Top K”的需求我绝大多数时候还是选标准库函数而不是手写 partition。C 用nth_elementPython 用heapq.nlargestJava 用PriorityQueue。标准库经过无数场景打磨性能稳定、边界处理完善没必要重复造轮子。但为什么要学手写呢因为面试要考因为很多场景比如嵌入式、自定义数据结构、需要精确控制比较器的时候标准库并不总是够用那时候你能写对 partition 就是核心竞争力。最后分享一个我在实际使用中发现的小技巧用快速选择的 partition 函数不光能求第 K 大还能当“排序前的预处理”用。比如你只需要把数组前 100 个元素拿出来参与后续聚合就可以先 partition 一次让前 100 个元素成为全局最大的 100 个然后再对这 100 个排序。这个组合在性能和代码量之间找到了很好的 balance遇到类似需求时不妨试试。