LeetCode hot100 第215题“数组中的第K个最大元素”我在面试里考过别人也在被考的时候抓过瞎。题目本身一句话就能说清给定整数数组 nums 和一个整数 k返回数组中第 k 个最大的元素。听起来无非是排个序再数一下可真到了白板上手写解法层次一下子就拉开了——排序、小顶堆、快速排序的 partition 思想、复杂度推导全都能串起来。这篇文章我按自己刷题时的思考路径来写先做最直的排序法再讲堆最后落到平均 O(n) 的快速选择顺便把面试官最喜欢追问的几个坑一并聊透。1. 题目拆解第 K 大到底对应哪个位置1.1 先把这个例子彻底走一遍官方示例是[3,2,1,5,6,4]k 2输出 5。很多人第一次做会顺手按降序排[6,5,4,3,2,1]第 2 个元素恰好是 5没错。但如果统一用升序数组来看第 k 大元素其实对应升序数组的n - k位置n 为数组长度。还是这个例子升序排完是[1,2,3,4,5,6]n - k 6 - 2 4nums[4]正好是 5。这个换算很关键因为后面快速选择的实现直接依赖它我们要找的并不是“降序第 k 个”而是“升序数组里索引为 n - k 的那个数”。第 1 大对应最后一个位置第 n 大也就是最小对应第一个位置。顺着这个思路边界条件就清楚了k 1 时取最大k n 时取最小其余情况在中间。再看一个有重复元素的例子[3,2,3,1,2,4,5,5,6]k 2答案是 5。这里有两份 5取哪个都行因为返回的是元素值而不是下标。有些同学第一反应是“先去重再取第 K 大”这是完全错误的理解。题目里的“第 K 大”在重复元素面前忽略重复带来的排名两个 5 都算同一个值排序后它们只是连续出现在相邻位置取值结果不受影响。1.2 为什么这题能进 hot100hot100 收录的题通常有两个特征要么面试高频要么能承载多个高频考点。第 215 题两头都占。它表面上是排序题实际上考的是复杂度思维和数据结构选型。我在面试中见过太多候选人直接一句“先快排然后取第 n-k 个”然后被追问“时间复杂度多少”“能不能更快”“如果数组大到内存装不下怎么办”就卡住了。这题真正想验证的能力有三层第一层知不知道排序解法能做出来第二层能不能意识到“排序做了大量无用功”第三层能不能把堆和快速选择的优劣讲清楚。能完整走完这三层的人基本可以认定对 TopK 问题是真的理解了而不是背过答案。1.3 面试官在等待的“标准答案结构”我自己做面试官时比较满意的回答结构大概是这样先给一个可运行的排序解法主动说时间复杂度 O(n log n)紧接着指出第 K 大只需要“部分有序”从这里引出大小为 k 的小顶堆把复杂度降到 O(n log k)如果面试官继续追问 O(n) 是否可行再展示基于 quickselect 的思路。这个递进过程比直接丢一个最优解出来更容易获得认可。2. 三种主流解法的原理对比与选型逻辑2.1 排序法先做出来再谈优化排序法是门槛最低的实现LeetCode 上也能 AC因为题目数据规模不大。JS 里最容易写的是function findKthLargest(nums, k) { nums.sort((a, b) b - a); return nums[k - 1]; }或者用升序排序返回nums[n - k]。两种写法都成立但我个人更推荐升序写法原因是它和“第 k 大 升序索引 n - k”这条规律直接对应后面理解快速选择的 target 时会少一层弯弯绕。复杂度上排序法的时间是 O(n log n)空间取决于语言内置排序的实现比如 V8 对数组排序会用 TimSort一些情况下额外空间是 O(n)。面试官追问的第一个问题几乎必然是“你比完全部元素就为了取一个位置上的值是不是浪费了”这句话就是引导你往堆和快速选择上走的信号。2.2 堆解法TopK 问题里最稳的方案堆解法的经典描述是维护一个大小为 k 的小顶堆遍历数组时如果堆没满就直接放入如果堆满了且当前元素比堆顶大就用当前元素替换堆顶。遍历结束后堆顶就是整个数组中第 k 大的元素。想明白为什么是“小顶堆”可以从语义上下手我们要从所有元素中挑出“最大的 k 个”这 k 个里最小的那个恰好就是第 k 大。维护一个 k 大小的小顶堆等于一直让最小的候选留在堆顶随时可以被更大的值顶掉。如果你用大顶堆去维护堆顶会成为最大的元素但你反而不知道“当前第 k 大到底是谁”因为更小的元素可能已经混在堆里了。时间复杂度是 O(n log k)因为每个元素最多触发一次堆化堆的高度是 log k。空间复杂度是 O(k)。和排序法比它在 k 远小于 n 的时候优势明显更重要的是它天然支持流式数据——如果输入不是一次性给出的数组而是一个不不断吐出数字的流堆解法可以只保留 k 个元素内存占用恒定。这是排序法做不到的。2.3 快速选择利用 partition 跳过整个分支快速选择quickselect是更激进的优化。它基于快速排序的 partition 操作一次 partition 之后pivot 会落到它最终应该在的位置左侧都比它小右侧都比它大。既然我们已经知道目标索引是 n - k那么每次 partition 后只判断 pivot 位置如果 pivot 索引正好等于 n - k直接返回如果小于目标索引说明答案在右侧只递归处理右侧如果大于目标索引说明答案在左侧只递归处理左侧。每次递归只需要处理其中一侧所以总工作量大约为 n n/2 n/4 ...等比数列求和收敛到 2n也就是平均 O(n)。这是它相比排序法最大的优势。代价是它不稳定最坏情况每次 partition 都选到当前区间的最小值或最大值导致划分极度不平衡复杂度退化到 O(n^2)。缓解手段主要是随机选 pivot或者先对数组做一次 shuffle把有序数组的极端情况打散。面试里能主动说出“选择随机 pivot 是为了避免最坏情况”是一个很加分的细节。2.4 三种方案横向对比解法平均时间复杂度最坏时间复杂度空间复杂度是否修改原数组适用场景排序法O(n log n)O(n log n)O(1) 或 O(n)是数据量小、代码优先、能过题就行堆解法O(n log k)O(n log k)O(k)否海量数据、流式输入、k 远小于 n快速选择O(n)O(n^2)O(1)是单次查询、内存受限、平均性能要求高注意“是否修改原数组”这一列。LeetCode 的判题系统只关心返回值不会让你复用原数组所以修改无伤大雅。但真实业务里原始数组可能还有别处要用这时候要么复制一份再 partition要么老老实实选堆解法。这也是我在工程上经常优先写堆的原因之一。3. 手写实现与关键细节逐行拆解3.1 快速选择的完整 JS 实现先给一套我实测很好用的代码迭代写法避免递归深度问题function findKthLargest(nums, k) { const n nums.length; const target n - k; let left 0; let right n - 1; while (left right) { const pivotIndex partition(nums, left, right); if (pivotIndex target) { return nums[pivotIndex]; } else if (pivotIndex target) { left pivotIndex 1; } else { right pivotIndex - 1; } } return -1; } function partition(nums, left, right) { const pivot nums[left]; let i left; let j right; while (i j) { while (i j nums[j] pivot) { j--; } nums[i] nums[j]; while (i j nums[i] pivot) { i; } nums[j] nums[i]; } nums[i] pivot; return i; }这套分区写法叫做“挖坑法”。先取nums[left]作为 pivot左侧指针 i 和右侧指针 j 相向移动。右侧先动找到第一个小于 pivot 的值把它填到 i 的位置然后左侧动找到第一个大于 pivot 的值把它填到 j 的位置。最终 i 和 j 相遇的位置就是 pivot 的家。外层用 while 迭代而不是递归是因为快速选择最坏情况递归深度可能达到 n递归版在面试白板上没问题但在真实环境里有可能栈溢出。迭代版是在工程习惯和可读性之间取的平衡。3.2 partition 的等号问题藏着最常见的坑这段代码里nums[j] pivot和nums[i] pivot的等号不是随手写的。如果去掉等号遇到大量与 pivot 相等的元素时内层循环会频繁提前退出挖坑和填坑的顺序会变得混乱分区结果不稳定极端情况下会让整个算法更容易退化。保留等号的意思是等于 pivot 的元素在扫描时直接被跳过让两个指针更干脆地相遇最终 pivot 左右两边各自由严格的“小于”和“大于”决定。另一种常见的 partition 写法是单指针扫描法Lomutofunction partition(nums, left, right) { const pivot nums[right]; let i left; for (let j left; j right; j) { if (nums[j] pivot) { [nums[i], nums[j]] [nums[j], nums[i]]; i; } } [nums[i], nums[right]] [nums[right], nums[i]]; return i; }它的代码更短但每找到一个小于 pivot 的值就做一次交换交换频率更高。挖坑法的赋值是“跳跃式”的更能模拟快排的原地性能。两个版本都能 AC我建议你至少能各写一遍因为面试官可能会让你解释“为什么这个 partition 是稳定的/不稳定的”。3.3 堆解法的完整手写版本虽然多数语言都有现成优先队列但面试时被要求手写堆也很常见。这里给一个 JS 的最小堆实现function findKthLargest(nums, k) { const heap new MinHeap(); for (const num of nums) { if (heap.size k) { heap.push(num); } else if (num heap.peek()) { heap.pop(); heap.push(num); } } return heap.peek(); } class MinHeap { constructor() { this.data []; } get size() { return this.data.length; } peek() { return this.data[0]; } push(val) { this.data.push(val); let i this.data.length - 1; while (i 0) { const parent Math.floor((i - 1) / 2); if (this.data[parent] this.data[i]) break; [this.data[parent], this.data[i]] [this.data[i], this.data[parent]]; i parent; } } pop() { const top this.data[0]; const last this.data.pop(); if (this.data.length 0) { this.data[0] last; let i 0; while (true) { const left i * 2 1; const right i * 2 2; let min i; if (left this.data.length this.data[left] this.data[min]) min left; if (right this.data.length this.data[right] this.data[min]) min right; if (min i) break; [this.data[i], this.data[min]] [this.data[min], this.data[i]]; i min; } } return top; } }这里有两个细节值得注意。push 时新元素先放到数组末尾再不断和父节点比较如果比父节点小就上浮。pop 时把最后一个元素挪到堆顶再和左右孩子中较小的那个下沉比较。处理相等元素时如果新元素等于堆顶replace 不 replace 都不影响最终值但为了减少堆操作我通常只在num heap.peek()时才替换。3.4 各语言的“作弊版”答案刷题阶段合理使用内置工具能省不少时间面试时也可以先说思路再用 API 验证。Pythonheapq.nlargest(k, nums)[-1]一行搞定内部就是堆。Cnth_element(nums.begin(), nums.begin() n - k, nums.end())然后取nums[n - k]底层就是快速选择的思想。JavaPriorityQueueInteger默认是小顶堆维护 k 个元素即可。不过我不建议直接把“作弊版”当作最终答案。它们的价值在于可以帮你快速验证思路但一旦面试官追问原理你还是要能回到手写的 partition 和堆上。4. 实战中容易翻车的典型问题4.1 partition 死循环与越界排除最常见的错误是内层 while 忘记加i j条件或者等号写反。比如while (nums[j] pivot) { j--; }数组越界一次可能不报错数据一变就出问题。我排查这种 bug 的经验是先拿一个全相等的数组比如[2,2,2,2]手动走一遍 partition如果 i 和 j 没能严格相遇十有八九是等号或范围条件写错了。另一个排查方法是打印每次 partition 后的数组和返回值对比目标索引快速定位是哪一侧的选择逻辑出了问题。4.2 第 K 大和第 K 小索引换算混乱给一个速查表目标升序排序后的索引快速选择 target第 1 大n - 1n - 1第 k 大n - kn - k第 n 小n - 1n - 1第 k 小k - 1k - 1很多人会把第 k 小当成n - k或者把第 k 大当成k - 1直接套进快速选择。一个不容易错的理解方式是升序数组左边小右边大第 k 小“从左边数”是 k - 1第 k 大“从右边数”是 n - k。先写下升序数组的例子再填索引基本不会绕晕。4.3 重复元素多时的性能退化前面提过快速选择在极端重复数据下可能退化到 O(n^2)。比如一个全是相同值的数组挖坑法分区后 pivot 每次都落在区间头部每次只能排除一个元素退化成逐一遍历。堆解法在这种场景下完全不受影响仍然是 O(n log k)。所以我在面试里会说这样一句话“如果数据中重复值占比很高或者无法接受 O(n^2) 的最坏情况我会选堆如果更在意平均性能和内存我用随机化的快速选择。”这种“带着场景选算法”的表达比单纯背结论更能体现工程思维。4.4 围绕数组操作的几个隐藏坑这道题虽然只要求“找数”但对数组基本功的要求一点不少。先说 JS 的sort()。它默认按字符串 Unicode 码点排序不传比较函数时[1, 10, 2].sort()的结果是[1, 10, 2]。所以用排序法时必须写nums.sort((a, b) a - b)或(a, b) b - a。这个点几乎每个 JS 面试都会顺带考到。再说数组切片法。Python 写sorted(nums)[-k]很直观C 里nth_element也很好用但注意它们大多会修改或复制数组。如果你在做一道不允许修改原数组的题要么return [...nums].sort((a, b) a - b)[n - k]复制一份再排要么老老实实走堆解法。还有很多人会把“数组去重”和第 K 大混在一起。题目没有要求去重重复值就按重复值算上文已经有示例。数组去重是另一类题常配合哈希表、ES6 的 Set 或者双指针处理别被这些衍生概念带跑偏。5. 面试现场怎么演以及这道题的延伸5.1 一段模拟面试的演进过程假设面试官出了原题候选人 A 的回答是 “我先排序然后取nums[n-k]。” “复杂度是多少” “O(n log n)。” “还能优化吗” “可以用堆维护大小为 k 的小顶堆O(n log k)。” “还有吗” “还可以用快速选择平均 O(n)。”这已经是一个合格的演进路线。如果候选人能接着说出“快速选择最坏 O(n^2)所以我面试时更推荐堆因为它是稳定 O(n log k)”那就更完整了。真实面试中“主动给出场景取舍”比“背最优解”更被看重。5.2 复用第 215 题思路的常见题目剑指 Offer 40最小的 k 个数。本质就是第 k 小快速选择或堆都行。LeetCode 347前 K 个高频元素。先用哈希表统计频次再对频次做 TopK。LeetCode 295数据流的中位数。两个堆一个最大堆一个最小堆思路从“第 K 大”直接延伸。LeetCode 973最接近原点的 K 个点。同样是 TopK只是比较对象换成了欧几里得距离。把 215 题吃透相当于把整套 TopK 问题的骨架拿下了。后面遇到“找第几大”“找前几小”“按某种指标取前 K”的题本质上都是同一套思考路径。5.3 我个人建议的刷题方式不是做完 3 个解法就收工而是每写一遍都问自己三个问题这个解法在最坏情况下会发生什么如果输入变成流式数据它还能不能工作如果 k 接近 n它还有没有优势我通常会用同一道题分别用排序、堆、快速选择各写一遍对比耗时和代码可读性再顺手把“第 k 小”的换算也写一遍。这样折腾下来遇到类似题基本只要想清楚 index 换算就能动手。以我个人的刷题和面试经验第 215 题真正重要的不是答案本身而是它在“暴力-优化-最优”这条路径上走得很完整。最后再分享一个小习惯看到“第 K 个”字样的题目先别急着写排序停下来问自己三个问题——能不能只处理部分数据能不能借助堆保留 K 个候选能不能用一次 partition 直接定位想清楚这三问TopK 类题目就再也没什么能难住你的了。