刷算法题卡到第33天遇到的题目是 LeetCode 215 题数组中的第 K 个最大元素。这道题几乎是所有算法训练计划里的“钉子户”面试出现频率极高而且解法多到能撑起一次完整的技术复盘排序能做、堆能做、快速选择能做甚至还能延伸到海量数据 TopK 和流式数据处理。这篇文章就把我在 Day33 这天的完整思路、手写代码、踩过的坑和后续扩展一起整理出来给同样在刷题的朋友做个参考。1. 先别急着写代码这道题到底在考什么1.1 题目本身是个什么玩意儿题目描述不复杂给定一个整数数组 nums 和一个整数 k返回数组中的第 k 个最大的元素。这里最关键的一点是它说的是“第 k 个最大”而不是“第 k 个不同的最大”。什么意思举个例子数组 [3, 2, 1, 5, 6, 4]k 2返回第 2 大的元素排序之后是 [6, 5, 4, 3, 2, 1]第 2 大就是 5。但如果数组是 [3, 3, 3, 1]k 2答案还是 3因为它指的是排序后从大到小数第二个位置上的值重复元素要按位置计算不是按去重后的唯一值算。这个理解一旦偏差后面的实现全错。题目的约束条件通常注意两个一是 k 的取值范围是 1 到数组长度二是数组长度可能比较大所以算法的时间复杂度有讲究。直接调库排序当然能过但如果你只写出这一种解法面试官大概率会追问一句“能不能优化到 O(n)”那一瞬间你就知道这道题不是考你会不会调用 sort而是考你对排序算法本质、堆结构和快排 partition 的理解有多深。1.2 为什么它值得单独开一天手动实现刷了三十多天题之后我越来越觉得有些题目值得“过三遍”第一遍看思路第二遍默写代码第三遍专门研究它的变体和边界。215 题就属于必须过三遍的题目因为它是整个 TopK 问题族谱的核心。TopK 问题是算法面试的常客后面还有“前 K 个高频元素”“数据流中的第 K 大元素”“最小的 K 个数”“有序矩阵中的第 K 小元素”等等几乎每一道都能和 215 题搭上关系。如果你能在 215 题上把堆和快速选择练熟后面的变体做起来会顺畅得多。反之如果这道题只背个 sort 提交就算完后面遇到流式数据场景你会发现自己面对“动态插入 查询第 K 大”毫无头绪。另外这道题也是区分“背题党”和“理解型选手”的分水岭。它没有复杂的递归套递归也没有动态规划的状态转移就一个数组、一个 k、一个目标值但每种做法的代码只在几行之间差别却很大。能把复杂度、稳定性、适用场景讲清楚的人说明是真的吃透了基础数据结构。1.3 我在 Day33 这天的拆题步骤我个人的刷题习惯是拿到题先不看题解按三个问题走一遍暴力解法长什么样复杂度多少我学过哪些数据结构能优化暴力解法这道题和我前两天刷过的什么题有相似之处第一个问题很好回答排序之后按下标返回O(n log n)。第二个问题能想到堆因为“动态维护 TopK”是堆的经典语义。第三个问题我在 Day30 左右刚刷过快排相关的题目对 partition 的写法还算熟所以能意识到快速选择这条路。这种拆题方式可能看起来慢但坚持下来会发现记忆特别牢。我强烈建议你刷题时不要养成“三分钟想不出来就看题解”的习惯至少给自己十五分钟的完整思考时间。很多时候答案不是靠灵感而是靠“你脑子里已经有什么工具”的检索过程。2. 三种典型解法逐个拆排序、堆、快速选择2.1 解法一排序后按下标取最简单但不能只会这个先给最直觉的写法class Solution: def findKthLargest(self, nums: List[int], k: int) - int: nums.sort() return nums[-k]就这三行。升序排序之后倒数第 k 个就是第 k 大。如果数组长度是 n那么倒数第 k 个元素对应的索引是 n - k写成 nums[-k] 也等价。这个方案的代码量几乎为零但你必须清醒地知道它的问题排序是整个数组时间复杂度 O(n log n)。如果面试里遇到的是一个小数组这样写完全没问题甚至面试官不会说什么——前提是你得主动补一句“这是最简单的解法我还可以用堆优化到 O(n log k)或者用快速选择优化到平均 O(n)”。我自己在面试模拟时最怕的状态就是一上来只会 sort面试官问到复杂度分析只能憋出一句“sort 底层是优化过的快排”。记住sort 不是不行它必须作为一个“解法选项”存在而不是唯一会写的代码。另外排序解法还有一个隐藏细节nums.sort() 是在原数组上原地排序会修改输入数组。有些面试场景会明确说“不能修改原数组”那就不能直接用 sort需要复制数组再排。复制数组的空间是 O(n)这又是一个可以和面试官讨论的延伸点。2.2 解法二小顶堆维护 TopK面试里的标准答案之一用堆的思路很聪明我只需要知道最大的 k 个元素是谁不需要知道其余的 n-k 个元素的顺序。那就维护一个大小为 k 的小顶堆堆顶永远是这 k 个元素里最小的那个所以当堆里塞满 k 个元素之后堆顶就是当前已扫描数据中的第 k 大。Python 里直接用 heapq 模块import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) - int: min_heap [] for x in nums: if len(min_heap) k: heapq.heappush(min_heap, x) elif x min_heap[0]: heapq.heapreplace(min_heap, x) return min_heap[0]逻辑拆开讲前 k 个元素直接入堆不用比较。从第 k1 个元素开始如果它比堆顶大说明它比当前堆里的最小值更值得留在 TopK 里于是替换堆顶如果它比堆顶小或相等直接跳过因为它不可能成为前 k 大。这里最容易犯迷糊的点是“为什么用小顶堆而不是大顶堆”。如果是大顶堆堆顶是最大的元素你没法快速知道“当前第 k 大是谁”因为堆里最大的那个给了堆顶剩下的 k-1 个是无序状态反而查不出第 k 大。小顶堆把最小界放在堆顶恰好就是第 k 大的“门槛”。这个思维要转过来维护 TopK想要快速淘汰必须知道“最差的那个谁”也就是所有候选里的最小值。复杂度方面每个元素入堆一次堆大小不超过 k每次堆操作 O(log k)整体 O(n log k)。当 k 远小于 n 时这个方案比排序快得多当 k 接近 n 时堆方案退化成 O(n log n)优势不在。堆方案真正的杀手锏是它不需要一次性拿到全部数据可以边读取边处理天然适配数据流。面试里只要提到“海量数据”“数据流”堆方案几乎就是默认答案。2.3 解法三快速选择 QuickSelect平均 O(n) 的经典思路快速选择的灵感来自快速排序的 partition 操作。一次 partition 做完之后基准元素被放到了它排序后的最终位置上而且它左边的元素都不大于它右边的元素都不小于它。既然知道了某个位置的“最终身份”就可以只往一边递归下去找目标这样平均时间复杂度降到了 O(n)。先附上一份可以直接跑的快速选择代码class Solution: def findKthLargest(self, nums: List[int], k: int) - int: def partition(left, right): pivot nums[left] i, j left, right while i j: while i j and nums[j] pivot: j - 1 nums[i] nums[j] while i j and nums[i] pivot: i 1 nums[j] nums[i] nums[i] pivot return i n len(nums) target n - k left, right 0, n - 1 while True: pos partition(left, right) if pos target: return nums[pos] elif pos target: left pos 1 else: right pos - 1这里的 partition 用的是“挖坑填数”的思路先把最左边元素拿出来当基准原位置就成了坑从右边找比基准小的填到坑里再从左边找比基准大的填到右边新空出的位置最后把基准放回相遇点。整个循环控制条件是 i j避免左右越界或无限循环。核心换算关系升序排序后第 k 大元素在索引 n - k 的位置上这是一个从 0 开始的下标。快速选择的目标不是“排好全数组”而是让这个目标索引处的元素就位。每次 partition 会得到一个位置 pos如果 pos 正好等于 target直接返回如果 pos 小于 target说明目标在右半段如果 pos 大于 target目标在左半段。一次只处理一边这就是它比排序快的原因。平均复杂度是 O(n) 吗严格算一下第一轮 partition 要扫描 n 个元素第二轮扫描大约 n/2 个第三轮 n/4 个……加起来是 n n/2 n/4 ... 2n所以常数不大平均确实是 O(n)。最坏情况则退化到 O(n^2)比如数组已经有序而每一次选的基准都恰好是当前段的最小值或最大值那样你每次只能排除一个元素扫描量变成 n (n-1) (n-2) ...等差数列和就是平方级。2.4 三个方案怎么选我常用的决策表决策不能靠“灵光一现”我一般按下面这个表选方案场景推荐方案理由面试开头要求快速出代码排序三行写完先保证有解面试官要求优化时间复杂度快速选择期望 O(n)不依赖额外空间数据是流式的不能一次性读入堆在线处理空间 O(k)数组很大k 很小堆不用排序全部空间也小数组很大而且要求稳定最坏复杂度BFPRT理论最优但工程上很少写需要原地实现不能改原数组排序副本或堆快速选择会修改数组结构这里多说一句 BFPRT它通过“取中位数的中位数”作为基准能把快速选择的最坏情况也拉到 O(n)但实现起来代码量大、常数因子也大实际工程里基本用不到。面试中知道它的名字和思想就够了不用强求现场写出来。3. 快速选择的核心细节与工程改造3.1 partition 的边界为什么容易写崩快速选择的代码核心是 partition但也是翻车重灾区。我见过身边同事在在线笔试里写出死循环、数组越界、结果不对最后都出在几个细节上。第一内层两个 while 的条件一定要带 i j。很多人从快排模板里抄代码会把条件写成while nums[j] pivot: j - 1不带 i j。在快速排序里可能偶尔能跑对但在快速选择里当 target 恰好就在边界附近时j 可能一路减到 left 之外直接索引越界。第二等号的处理。我上面代码里判断nums[j] pivot和nums[i] pivot时都带了等号这样在数组存在大量和 pivot 相等元素的情况下指针也能稳定移动。如果去掉等号遇到重复元素时 i 和 j 可能原地不动陷入死循环。第三挖坑填数法和左右交换法的混用。有些人写快排用的是“左右同时找然后交换”的写法这就跟挖坑填数法混了代码里一会 nums[i] nums[j]一会又 swap最后基准位置都不一定对。我后来给自己立了一个规矩选择一种 partition 写法练到肌肉记忆面试和笔试统一用它。我选的就是挖坑填数法因为它的状态更新是双向填空逻辑上不容易丢元素。3.2 第 k 大与第 k 小的换算90% 的人会记混面试时经常有“换个说法考你”的情况求第 k 大的元素本质就是求第 n-k1 小的元素。为什么从小到大排序后第 n-k1 小的位置从 0 开始索引是 (n-k1) - 1 n-k这和第 2.3 节里的 target n - k 完全对上。我建议你把这张换算表刻进脑子升序排序数组中倒数第 k 个元素的索引len(nums) - k它是第 len(nums) - k 1 小它是第 k 大很多题解里直接用 target len(nums) - k有些用 target len(nums) - k 1还有人用 k - 1看起来差别只有 1实则是混淆了“第几个”和“索引”的区别。所以写代码的第一行先注释清楚target 是目标索引不是目标排名。3.3 随机化基准把最坏情况变成小概率事件快速选择最怕数组已经有序而且你每次取的基准又是开头或结尾元素那每轮只能排除一个位置复杂度直接爆炸。解决思路很简单别固定取最左元素做基准而是随机挑一个元素把它交换到 left 位置再执行原来的 partition。改造代码就多三行import random def partition(left, right): rand_idx random.randint(left, right) nums[left], nums[rand_idx] nums[rand_idx], nums[left] pivot nums[left] # 后续逻辑不变这样在概率上几乎不可能出现每次都选到极端基准的情况。随机化之后快速选择在任意输入上的期望复杂度都是 O(n)。虽然最坏情况依然存在但是概率极低工程上完全够用。如果你不想引入随机数模块另一种做法是三数取中取 left、mid、right 三个位置的中位数当基准也能显著改善有序数组上的表现。随机化的好处是代码改动更少也不需要考虑三个位置的计算。需要特别提醒随机化不是“为了炫技”而是让算法的平均复杂度从“平均输入保证”变成“任意输入的概率保证”。面试时能主动提到这一点是加分项因为它说明你不只会背模板而是真正理解算法退化条件。3.4 重复元素与全相等数组快速选择还能扛住吗很多人一想到快排的 partition 就担心重复元素。来我们推演一个极端情况数组全是 3k 1目标是索引 n - 1。partition 从左往右扫因为所有元素都满足nums[i] pivoti 会一直往右走到 right同时 j 向左走到不能走为止。最终 i 和 j 会在 right 附近相遇返回的位置基本正常。由于我带了等号指针一定会移动不会死循环。最终 pos 可能是数组末尾附近然后根据 target 和 pos 的关系决定递归方向。这里有个隐藏心得全相等数组是验证 partition 实现是否健壮的标准测试用例。我每次写完快速选择都会先拿[1]*n这种数组跑一遍如果它不超时、不越界、能选出正确值那绝大多数输入都不会有问题。另外重复元素也会带来一个面试追问点“如果数组里有很多重复值你的快速选择会不会退化”如果你用的是三路快排把相等元素单独归到一个区域可以更稳定。但这个实现复杂度明显更高需要把 partition 改成三个区间小于、等于、大于。面试时间有限时不推荐现场写三路版除非你提前练过几十遍。提到“可以改为三路快排优化”这个概念就够了面试官会懂的。4. 实战中常见的坑与排查思路4.1 终止条件什么时候可以安全返回快速选择如果写的是递归版本很多人搞不清递归到底在哪一层返回结果。其实无论递归还是迭代终止条件都可以统一成一句话目标索引所在的区间已经确定只有一个元素或者经过 partition 后 pos 直接命中 target。我最初写递归版的时候习惯在函数开头判断if left right: return nums[left]。这个判断其实是兜底真正让函数结束的还是pos target那条路径。但兜底必须有否则在区间缩到空的时候下一层递归的 left 可能大于 right凭空造出越界。迭代版虽然没有递归栈的问题但要注意循环不是固定次数而是靠 left 和 right 的收敛来退出。如果写完循环体之后忘记更新边界或者更新逻辑写反就会出现“区间永远不变”的死循环。我自己的习惯是在每次循环结束前打印 left、right、pos肉眼确认区间确实在变小。4.2 一次性通过率低我踩过的三个坑全公开先说第一个坑把 partition 内的i和j搞混。初始化是 i left, j right但有些人会把 i 写成 0j 写成 n-1。第一次调用无所谓可一旦进入第二次分治i 会从 0 开始、j 会越界到整个数组末尾直接破坏分区逻辑。记住partition 的左右边界是调用者传入的不是写死的。第二个坑在 partition 结束之后忘了把基准放回 i 的位置。挖坑填数法的最后一步nums[i] pivot是必须的。少了这行基准值直接丢失数组里会多出一个坑后续的结果完全是错的。这种 bug 特别隐蔽因为数组里元素数量不变只是某个位置被覆盖了两次。第三个坑快速选择修改了原数组。如果题目或面试官要求“不能改变原数组内容”快速选择就不能直接用在原始数组上需要先 copy。很多人忽略了这一点提交代码后才发现原数组被动过。我建议在实现前就先问清楚约束这是工程素养的一部分。4.3 时间超限排查清单如果你自己写好了快速选择但提交后 TLE超时按下面顺序查是不是内层 while 的条件漏了 i j漏掉后指针可能越界也可能在某些输入上出现极端行为。是不是基准选择固定在最左而测试用例里有大量有序数据加随机化。是不是递归没有收敛导致死循环检查区间更新逻辑。是不是每次循环都重新创建数组切片如果有人写nums[:pos]之类来分治复杂度退化成 O(n^2)而且额外空间爆炸。必须用下标在原数组上操作。是不是 k1 或者 kn 这类极端输入跑到了最坏情况可以单独加 if 判断比如 k1 时直接返回 max(nums)kn 时返回 min(nums)。我用过最笨但有效的排查方法本地把 TLE 的测试用例复制下来打印每次 partition 后的数组状态人工核对几次就能定位问题。4.4 堆方案在海量数据场景中的真实优势快速选择很优秀但它有一个先天限制需要数组一次性全部载入内存。海量数据场景下比如一百亿条日志、百亿级别的用户行为记录你不可能把所有数据拉到内存排序甚至快速选择也挤不进内存。堆方案的优势这时候就体现了它的核心存储只有 k 个元素。k 等于 10堆就占 10 个位置k 等于 1000堆就占 1000 个位置。无论数据量是十万还是一亿只要你能逐个读取数据堆就能在线输出第 k 大。这也是很多大数据框架处理 TopN 的基本套路map 端先维护一个局部小堆再汇总合并。我工作里遇到过一个真实场景某天要统计某个统计周期内访问量排名前 100 的 IP直接全局排序显然不行数据文件成千上万放在磁盘上。解决方案就是分块读入每个块用堆维护局部 Top100最后再到内存里合并所有块的 Top100。整个过程内存占用常量级速度还很快。所以堆方案不只是一道题里的选项它是“数据流 / 海量数据”这类题目的通解。面试时如果你能把这一层延展说出来能明显体现出算法思维和工程眼界的差距。5. 从第 215 题延伸出去的算法能力5.1 TopK 问题家族一题串起来一串做完第 215 题你会发现好多题目都像它的亲戚最小的 K 个数把 target 从 n-k 改成 k-1 就是同一套快速选择逻辑。前 K 个高频元素先统计频次再在频次数组上做 TopK用的还是堆或快速选择。数据流中的第 K 大元素本质是动态维护一个小顶堆插入一个元素、调整一次堆、返回堆顶。有序矩阵中的第 K 小元素可以堆做也可以二分答案结合计数。找两个有序数组的中位数中位数就是第 k 小的特例k 落在中间位置。你在刷这些题目时会发现核心代码都是“堆”或者“partition”变的是数据形态和统计口径。所以第 215 题真的值得认真吃透它的价值远超题目本身。5.2 快速选择思想在工程里的影子快速选择不只是刷题算法很多数据库、搜索引擎库、中间件在排序和选中位数的场景里都有类似思路。比如某个分布式存储系统需要计算分位数不可能把所有数据全排序而是采样后做近似快速选择拿到某个比例位置的值。这个场景里处理的数据量大、精度要求不高快速选择就是完美解法。再比如很多数据分析工具里的 median、percentile 计算在内存可以放下数据时会直接用快速选择的变种因为它的平均复杂度确实比全排序低常数因子也很小。理解了快速选择你去看那些库的源码或论文脑子里会有一个清晰的轮廓。有一种说法是快速排序是排序算法里工程现实世界用得最广的而快速选择就是它“只做一半工作”的聪明版。你在面试里能把快速排序和快速选择的关系讲清楚这本身就是一种深度的体现。5.3 面试追问链怎么用一道题展示自己的深度模拟面试时我总结了一条从 215 题延伸出去的追问链你可以照着自测第一层能写出排序解法讲出时间、空间复杂度。第二层能写出堆解法讲出为什么要用小顶堆而不是大顶堆以及 O(n log k) 的推导。第三层能写出快速选择讲出平均 O(n)、最坏 O(n^2) 的原因。第四层能指出快速选择会修改原数组回答如何在不修改原数组的情况下完成。第五层能主动谈随机化基准、三路快排优化以及 BFPRT 思路。第六层能把题目的思想迁移到海量数据 TopK 和数据流场景。能到第四层就已经超过绝大多数准备了。第五、第六层属于“高手区”你未必每次都要讲但你要保证被追问时脑子里有料。这种递进式的准备方式比背十道题答案要高效得多。5.4 给第 34 天之后的自己留个记录刷题打卡到第 33 天最大的感受是算法题的提升不是靠“量”而是靠“每道题多走一步”。比如第 215 题普通做法是 sort写完提交就完多走一步把堆、快速选择、随机化、复杂度对比都吃透这道题就变成了一个知识网络节点后面所有 TopK 变体都能挂到这个节点上。如果今天是你的 Day1 或者 Day10我的建议是不要急着追求一天刷五道题可以试着一天对一个题型穷尽所有解法。今天把第 K 大吃透明天遇到第 K 小你只需要改动一个索引换算就能秒杀今天记住小顶堆的语义后天做前 K 个高频元素你会发现思路完全通。这样刷题三十天之后你会形成自己的解题弹药库而不是题库流水账。我自己现在会在每道题做总结时多写一行“延伸思考”如果数据量变成一千倍怎么办如果输入变动态怎么办如果要求稳定排序怎么办这些问题不一定当场都有答案但它们会成为后续刷题的引子。第 215 题的这行延伸思考已经帮我带出了至少四道变体题的正确思路这个方法我打算一直用到 Day100。