如果你刷到了hot100里的215题说明你大概率正在集中啃TopK这类问题。数组中的第K个最大元素题目描述不到一屏解法却基本串起了面试里所有“第K大/小”问题的套路排序能过堆能过但想跟面试官聊出亮点还得会快速选择Quickselect。这篇就按“暴力—优化—最优”的思路把这题彻底拆开从题意转换、复杂度推导到实际代码每个细节都尽量说透。这篇内容适合三类人刚刷题想搞懂基础解法的新手准备面试想答出深度的同学以及想系统整理TopK问题做笔记的老手。不论你是用C、Java还是Python核心思路都一样代码我也尽量给出多种风格。读完后你不仅能拿下215题还能顺手解决一堆同类变体。1. 题目拆解第K个最大元素到底在考什么1.1 题意转换与索引对应先说说这道题最容易踩的第一个坑第K个最大元素“最大”这个词索引到底怎么对应给定一个无序数组nums和一个整数k要求返回数组中第k大的元素。比如[3,2,1,5,6,4]k 2答案是5。很多人会不假思索地写sort(nums.rbegin(), nums.rend()); return nums[k - 1];降序排序后第1大是nums[0]第2大是nums[1]所以第k大自然就是nums[k - 1]。这没问题。但另一种更隐蔽的写法是升序排序sort(nums.begin(), nums.end()); return nums[n - k];这里n - k是第k大元素在升序数组中的位置。举个例子[1,2,3,4,5,6]第2大是5下标是6 - 2 4指向5。很多新手栽在这里是因为把“第k大”和“第k小”搞混。第k大第n - k 1小从1开始计数如果从0开始计数就是下标n - k。这个转换一定要刻在脑子里后面做快速选择时天天要用。1.2 为什么这题高频出现面试官想听到什么LeetCode的hot100榜单本身就是从高频面试题里筛出来的215题长期位居前排不是因为它难而是因为它触及了一个核心能力如何在海量数据中只关注关键的一部分而不是处理全部数据。推荐系统里取热度前100的商品、排行榜取Top10用户、监控系统拉取最近5分钟的错误日志TopN本质都是TopK问题。面试官考这题表面上是考你会不会写堆、会不会分治实际上是想看你能不能根据数据规模选择合适算法——数据小直接排序数据大有内存压力就得上堆追求极致效率就得上快速选择。另外这题常常被当作多个难题的“地基”。数据流中的第K大元素、前K个高频元素、有序矩阵中的第K小元素本质上都能从215题的解法上做扩展。先把这题吃透后面几个变体你再看就会轻松很多。2. 解法一排序解法三分钟拿下拿分项2.1 升序排序与索引计算先看最快能写出来的版本C不到五行的标准答案class Solution { public: int findKthLargest(vectorint nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size() - k]; } };很多教科书喜欢让你降序排序取k-1下标但我更推荐升序排序取n-k下标。原因很简单C的sort默认升序少写一个反向迭代器也少一次思维转换。Java里用Arrays.sortPython里用sorted都是默认升序统一用n - k这套逻辑不容易乱。时间复杂度O(n log n)空间复杂度取决于排序实现一般在O(1)到O(log n)之间。对于线上面试来说先把排序解写出来拿住保底分再往下演进是性价比最高的策略。2.2 排序解法的性能评估和工程取舍排序解法的问题不是错而是“过于奢侈”。你只需要第k大的那一个数排序却把整个数组全都排好了。如果n是一百万、k是10你为了一个第10大的数把一百万个元素全部排了序纯属浪费。但工程上有个非常实用的技巧如果你的语言标准库里提供了部分排序函数直接用就是最优解。C的nth_element就是为此设计的它能在平均O(n)时间内把第n小的元素放到正确位置且保证它左边的元素都不大于它、右边的元素都不小于它class Solution { public: int findKthLargest(vectorint nums, int k) { nth_element(nums.begin(), nums.begin() k - 1, nums.end(), greaterint()); return nums[k - 1]; } };这段代码我不能建议你面试时直接写因为它“作弊”嫌疑太大了面试官大概率会追问你底层原理。但它告诉我们一件事最终追求的性能目标就是O(n)级别而且不需要稳定排序全部数据。理解了这一点你就能顺畅地衔接到下面的堆解法和快速选择。3. 解法二堆解法TopK问题的标准姿势3.1 为什么维护大小为K的最小堆堆解法是TopK问题的招牌解法但有一个绕弯的点求第K大用的是大小为K的“最小堆”不是最大堆。不少同学第一次写的时候会写反维护了一个大小为K的最大堆结果堆顶是K个元素里最大的那个跟题目要的完全不是一回事。我用一句话解释清楚维护大小为K的最小堆让堆里始终保存“当前已经见过的元素中最大的K个”。因为堆顶是这K个元素里最小的也就是这K个元素的下界。等数组全扫完一遍堆顶就是所有元素里第K大的那个。打个比方你面前有100个人你要找出身高第3高的人。你手里只拿一张写着“我目前见过的最矮的Top3中的那个身高”的卡片。每遇到一个人如果这人比卡片上的数字高就扔掉卡片上的数字换这个人进来然后重新找出现在Top3里最矮的那个。等100个人都过完卡片上的数字就是第3高的身高。3.2 堆解法的代码实现与细节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(); } };有几个细节值得注意priority_queueint, vectorint, greaterint是C里构造小顶堆的固定写法很多人只记priority_queueint那就默认是大顶堆了结果正好反掉。当堆不满k个时无条件入堆堆满了以后只有比堆顶大的元素才有资格进来。元素等于堆顶时不需要处理因为进来再出去没有意义。最终返回堆顶这个堆顶就是当前堆里最小的元素但整个堆保存的是最大的K个所以堆顶恰好是第K大。Java里用PriorityQueueInteger默认就是小顶堆写起来更省事。Python里用heapq默认也是小顶堆。原理一模一样只是语法不同。3.3 堆空间与时间复杂度再优化堆解法的时间复杂度是O(n log k)每个元素进堆出堆一次堆操作是O(log k)。空间复杂度O(k)。这里有一个常常被忽略的优化方向当k远大于n/2时可以考虑反过来求第n - k 1小。比如数组长度是1亿让你求第99999999大的元素你要是维护一个99999999大小的小顶堆堆的操作成本就离谱了。这时候可以换思路第99999999大相当于第2小维护一个大小为2的“最大堆”扫一遍数组堆顶就是第2小也就是我们要的第99999999大。这个“反向思维”在很多TopK题里都通用面试时主动提出来是明显的加分项。4. 解法三快速选择期望O(n)的核心算法4.1 从快速排序到Quickselect的改造思路如果面试官在你给出堆解法后接着问“能不能再快一点”你要清楚他想要什么答案快速选择。快速选择的核心思想脱胎于快速排序的partition分区过程。快速排序每一轮选定一个基准值pivot把数组分成小于等于pivot和大于等于pivot的两部分然后对两边递归排序。快速选择只需要关心一侧如果pivot最终落到了我们要找的位置直接返回如果目标在左侧就只递归左侧如果目标在右侧就只递归右侧。另一侧完全不用管。正因为每次只需要处理一半的数据它的平均时间复杂度从快排的O(n log n)降到了O(n)。快速排序是“两边都要管”快速选择是“只管一边”这就是全部区别。4.2 partition分区函数的稳定实现先写一个标准的Lomuto分区原地重排数组返回pivot最终所在下标int partition(vectorint nums, int left, int right) { int pivot nums[right]; // 每次取最右边的元素作为基准 int i left - 1; // i指向最后一个“小于等于pivot”的位置 for (int j left; j right; j) { if (nums[j] pivot) { i; swap(nums[i], nums[j]); } } swap(nums[i 1], nums[right]); return i 1; }这里有个容易写错的地方i的初始值是left - 1不是0。因为分区函数可能会处理子数组而不是整个数组。如果你图省事写成int i 0那在递归到右半部分时分区逻辑会完全错乱。这个bug肉眼不好查跑起来数据一大就崩我见过不止一个同学卡死在这里。另一个常见错误是写成。如果你只让严格小于pivot的元素放到左边那等于pivot的元素会被堆到右边在大量重复元素的场景下分区会严重失衡递归退化。4.3 递归方向的判定与代码实现拿到分区函数之后整个快速选择的核心逻辑就是判断“要找的位置在分区的哪一侧”。这里我提供一个减少思维负担的写法把“第K大”统一转换成“第n - K 1小”然后求该位置的元素。转换成“第index小”之后递归方向的判断就变得特别直观如果pivot的最终下标等于index - 1说明pivot恰好就是我们要找的第index小元素直接返回如果pivot下标小于目标位置去右边找否则去左边找。class Solution { public: int findKthLargest(vectorint nums, int k) { int index nums.size() - k; // 第k大 → 第 (n-k1) 小 → 下标 n-k int left 0, right nums.size() - 1; while (left right) { int pivotIdx partition(nums, left, right); if (pivotIdx index) { return nums[pivotIdx]; } else if (pivotIdx index) { left pivotIdx 1; // 目标在右侧 } else { right pivotIdx - 1; // 目标在左侧 } } return -1; // 理论上不会走到这里 } };递归写法会更简洁但我个人更喜欢用while循环。为什么因为递归版本每递归一次都要重新拷贝边界参数栈深度在极限情况下可能到达O(n)而while循环完全避免了这个问题。面试时写循环版本还能顺带展示你对“递归转迭代”的理解。4.4 平均O(n)的来源与最坏情况兜底很多人背下来了“快速选择平均O(n)”但被问到“为什么最坏会变成O(n²)”就答不上来。这里解释一下。快速选择每次partition后期望只处理一半的数据。如果每次都能把数组差不多对半分那么总工作量是n n/2 n/4 ... 2n所以平均是O(n)。但如果你运气差每次pivot都选到了当前区间的最小值或最大值分区后左右两边极不平衡每次只能去掉一个元素那总工作量就是n (n-1) (n-2) ... O(n²)。避免退化有几种手段按实用程度排序随机选pivot每次从[left, right]随机取一个下标和nums[right]交换让最坏情况变成概率意义上的几乎不可能。这是工程上最推荐的方案实现成本最低。三数取中取左、中、右三个位置的中间值作为pivot能有效避免近似有序数组的退化。BFPRT算法中位数的中位数理论上能把最坏情况降到严格O(n)但常数巨大竞赛里都不太用面试时能说出来名字、解释思路就够了。我建议在笔试里直接用随机选pivot版。曾经有个同学用固定取右端点的版本去跑大规模近乎有序的测试数据直接超时换成随机pivot后一遍过。这种性能差异不是代码逻辑错误纯粹是pivot选择策略的问题。5. 实战踩坑超时、越界、死循环排查实录5.1 排序后索引算错——第K大不等于下标K有个使用排序解法常见的错误写了return nums[k]自己在本地用小数组测试时发现输出好像“差不多对”但一旦k恰好等于n就越界。第K大在下标上永远要记得“从1开始计数”和“数组从0开始计数”的错位。k1时应该是数组中最大值对应升序下标的n-1也就是n-k。kn时对应最小值升序下标0依然满足n-k 0。所以n-k这个公式在所有情况下都是自洽的。如果你非要用降序下标那就是k-1。这两个公式可以互相验证建议写在草稿纸上别靠心算。5.2 快速选择进死循环——分区边界没锁死快速选择一个隐蔽的坑是left pivotIdx 1和right pivotIdx - 1这两个更新语句看起来不起眼但缺一个或者写错一个程序就会陷入死循环。举个例子如果目标位置在左侧你写成left pivotIdx而不是pivotIdx - 1而pivot恰好又在目标右侧那下一轮partition的时候区间的左边界根本没变pivot还是同一个结果还是同一个无限循环。这个bug的可怕之处在于它不会立刻报错只是让程序卡住不动新手很难第一时间联想到是边界更新错了。排查技巧在while循环里打印每次的left、right和pivotIdx如果发现连续两次输出一模一样说明边界更新有问题沿着这个方向查准没错。5.3 重复元素导致分区失衡——pivot选择的处理如果数组里全是重复元素比如[5,5,5,5,5]取最右端pivot进行分区时的比较会让所有元素都跑到左边去partition返回的下标是right - 1。此时右侧区间为空递归方向判断会变得非常极端。这是快速选择在工程应用中一个真实的痛点。处理方式一般有两种换用双指针的双向分区Hoare分区让等于pivot的元素尽量均匀分布在两侧。保持Lomuto分区但配合随机pivot让重复元素导致的失衡在概率上被抹平。我个人的建议是笔试面试里优先使用随机pivot Lomuto分区代码短、思路清晰、重复元素场景下表现已经足够好。双指针分区虽然更稳但写错的概率也更高如果不是特别熟练不要在高压环境下临场尝试新写法。5.4 手写堆与标准库优先队列的选择有些学校作业或比赛环境禁用标准库容器逼着你手写堆。手写堆时最容易错的是“上浮/下沉”操作的边界条件下沉操作中子节点下标不能越界要判断child 1 heapSize是否存在右孩子。上浮操作中要确保当前节点不是根节点idx 0才能跟父节点比较。比较方向容易搞反求第K大我们维护的是小顶堆堆顶是“当前最大的K个里最小的”所以新元素比堆顶大才入堆不是比堆顶小入堆。如果允许用标准库我强烈建议直接用priority_queue或heapq。因为笔试环境拼的就是速度和准确率标准库堆经过无数人验证比自己手写的稳得多。手写堆可以作为理解原理的练习但没必要在限时场景里给自己加难度。6. 解法选型与TopK问题扩展6.1 面试时的回答节奏和代码风格建议面试回答这题时一个稳妥的叙述顺序是先排序再堆最后快速选择。每一步都主动交代复杂度并说明为什么下一步更优。这样既展示了基础扎实又展示了优化意识。举个标准的回答节奏“最先想到排序O(n log n)简单直接。但我们可以用大小为k的小顶堆把复杂度降到O(n log k)空间O(k)适合处理流式数据。如果数组已经全部加载在内存里且k很小或k很接近n堆的空间和操作都不划算用快速选择可以做到期望O(n)只需要O(1)的额外空间。”这段话本身就值很多分因为它体现了数据规模意识。代码风格上我建议变量名在保持简洁的前提下尽量要有含义别用a、b、c。面试官看你代码的时间可能比你写代码的时间还长清晰的命名就是在帮对方省时间。6.2 从215延伸出去的TopK变形题把215题的思路迁移开你会发现一大批题目其实在考同一个能力数据流中的第K大元素维护一个固定大小K的小顶堆每来一个新元素就走一遍“比堆顶大就替换”的逻辑。和215的区别就是数据不是一次性给出的而是源源不断来的。前K个高频元素先用哈希表统计频率再建立一个“按频率比较”的小顶堆堆里始终保存频率最高的K个。有序矩阵中的第K小元素可以利用堆来做多路归并也可以二分答案后用计数判断。里面二分答案的思路本质上也是一种“快速选择”思想的变体。数据流中的中位数维护一个最大堆和一个最小堆两堆大小相差不超过1中位数就是堆顶之一。这是215题堆解法的直接升级版面试出现频率也非常高。把这些题放在一起刷你会发现规律极其明显凡是要“第K”的先想能不能用堆凡是要“最值中的第K”的再想能不能做二分答案或快速选择。最后分享一个我个人的刷题习惯215题我前后写过不下十遍每次换一种语言、换一种分区写法、换一种堆的实现方式。直到有一次在闲聊时被问到“你有想过为什么快速选择的期望复杂度是O(n)而不是O(n/2)吗”我才意识到其实不少人连这个结论的来龙去脉都说不清。如果你也只能背结论建议现在就把快速选择的推导过程亲手写一遍——有些东西刷一遍不如手推一遍记得牢。这题就像一把万能钥匙真正掌握后TopK这一类问题对你来说就再也不会是难题了。
如果你刷到了hot100里的215题说明你大概率正在集中啃TopK这类问题。数组中的第K个最大元素题目描述不到一屏解法却基本串起了面试里所有“第K大/小”问题的套路排序能过堆能过但想跟面试官聊出亮点还得会快速选择Quickselect。这篇就按“暴力—优化—最优”的思路把这题彻底拆开从题意转换、复杂度推导到实际代码每个细节都尽量说透。这篇内容适合三类人刚刷题想搞懂基础解法的新手准备面试想答出深度的同学以及想系统整理TopK问题做笔记的老手。不论你是用C、Java还是Python核心思路都一样代码我也尽量给出多种风格。读完后你不仅能拿下215题还能顺手解决一堆同类变体。1. 题目拆解第K个最大元素到底在考什么1.1 题意转换与索引对应先说说这道题最容易踩的第一个坑第K个最大元素“最大”这个词索引到底怎么对应给定一个无序数组nums和一个整数k要求返回数组中第k大的元素。比如[3,2,1,5,6,4]k 2答案是5。很多人会不假思索地写sort(nums.rbegin(), nums.rend()); return nums[k - 1];降序排序后第1大是nums[0]第2大是nums[1]所以第k大自然就是nums[k - 1]。这没问题。但另一种更隐蔽的写法是升序排序sort(nums.begin(), nums.end()); return nums[n - k];这里n - k是第k大元素在升序数组中的位置。举个例子[1,2,3,4,5,6]第2大是5下标是6 - 2 4指向5。很多新手栽在这里是因为把“第k大”和“第k小”搞混。第k大第n - k 1小从1开始计数如果从0开始计数就是下标n - k。这个转换一定要刻在脑子里后面做快速选择时天天要用。1.2 为什么这题高频出现面试官想听到什么LeetCode的hot100榜单本身就是从高频面试题里筛出来的215题长期位居前排不是因为它难而是因为它触及了一个核心能力如何在海量数据中只关注关键的一部分而不是处理全部数据。推荐系统里取热度前100的商品、排行榜取Top10用户、监控系统拉取最近5分钟的错误日志TopN本质都是TopK问题。面试官考这题表面上是考你会不会写堆、会不会分治实际上是想看你能不能根据数据规模选择合适算法——数据小直接排序数据大有内存压力就得上堆追求极致效率就得上快速选择。另外这题常常被当作多个难题的“地基”。数据流中的第K大元素、前K个高频元素、有序矩阵中的第K小元素本质上都能从215题的解法上做扩展。先把这题吃透后面几个变体你再看就会轻松很多。2. 解法一排序解法三分钟拿下拿分项2.1 升序排序与索引计算先看最快能写出来的版本C不到五行的标准答案class Solution { public: int findKthLargest(vectorint nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size() - k]; } };很多教科书喜欢让你降序排序取k-1下标但我更推荐升序排序取n-k下标。原因很简单C的sort默认升序少写一个反向迭代器也少一次思维转换。Java里用Arrays.sortPython里用sorted都是默认升序统一用n - k这套逻辑不容易乱。时间复杂度O(n log n)空间复杂度取决于排序实现一般在O(1)到O(log n)之间。对于线上面试来说先把排序解写出来拿住保底分再往下演进是性价比最高的策略。2.2 排序解法的性能评估和工程取舍排序解法的问题不是错而是“过于奢侈”。你只需要第k大的那一个数排序却把整个数组全都排好了。如果n是一百万、k是10你为了一个第10大的数把一百万个元素全部排了序纯属浪费。但工程上有个非常实用的技巧如果你的语言标准库里提供了部分排序函数直接用就是最优解。C的nth_element就是为此设计的它能在平均O(n)时间内把第n小的元素放到正确位置且保证它左边的元素都不大于它、右边的元素都不小于它class Solution { public: int findKthLargest(vectorint nums, int k) { nth_element(nums.begin(), nums.begin() k - 1, nums.end(), greaterint()); return nums[k - 1]; } };这段代码我不能建议你面试时直接写因为它“作弊”嫌疑太大了面试官大概率会追问你底层原理。但它告诉我们一件事最终追求的性能目标就是O(n)级别而且不需要稳定排序全部数据。理解了这一点你就能顺畅地衔接到下面的堆解法和快速选择。3. 解法二堆解法TopK问题的标准姿势3.1 为什么维护大小为K的最小堆堆解法是TopK问题的招牌解法但有一个绕弯的点求第K大用的是大小为K的“最小堆”不是最大堆。不少同学第一次写的时候会写反维护了一个大小为K的最大堆结果堆顶是K个元素里最大的那个跟题目要的完全不是一回事。我用一句话解释清楚维护大小为K的最小堆让堆里始终保存“当前已经见过的元素中最大的K个”。因为堆顶是这K个元素里最小的也就是这K个元素的下界。等数组全扫完一遍堆顶就是所有元素里第K大的那个。打个比方你面前有100个人你要找出身高第3高的人。你手里只拿一张写着“我目前见过的最矮的Top3中的那个身高”的卡片。每遇到一个人如果这人比卡片上的数字高就扔掉卡片上的数字换这个人进来然后重新找出现在Top3里最矮的那个。等100个人都过完卡片上的数字就是第3高的身高。3.2 堆解法的代码实现与细节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(); } };有几个细节值得注意priority_queueint, vectorint, greaterint是C里构造小顶堆的固定写法很多人只记priority_queueint那就默认是大顶堆了结果正好反掉。当堆不满k个时无条件入堆堆满了以后只有比堆顶大的元素才有资格进来。元素等于堆顶时不需要处理因为进来再出去没有意义。最终返回堆顶这个堆顶就是当前堆里最小的元素但整个堆保存的是最大的K个所以堆顶恰好是第K大。Java里用PriorityQueueInteger默认就是小顶堆写起来更省事。Python里用heapq默认也是小顶堆。原理一模一样只是语法不同。3.3 堆空间与时间复杂度再优化堆解法的时间复杂度是O(n log k)每个元素进堆出堆一次堆操作是O(log k)。空间复杂度O(k)。这里有一个常常被忽略的优化方向当k远大于n/2时可以考虑反过来求第n - k 1小。比如数组长度是1亿让你求第99999999大的元素你要是维护一个99999999大小的小顶堆堆的操作成本就离谱了。这时候可以换思路第99999999大相当于第2小维护一个大小为2的“最大堆”扫一遍数组堆顶就是第2小也就是我们要的第99999999大。这个“反向思维”在很多TopK题里都通用面试时主动提出来是明显的加分项。4. 解法三快速选择期望O(n)的核心算法4.1 从快速排序到Quickselect的改造思路如果面试官在你给出堆解法后接着问“能不能再快一点”你要清楚他想要什么答案快速选择。快速选择的核心思想脱胎于快速排序的partition分区过程。快速排序每一轮选定一个基准值pivot把数组分成小于等于pivot和大于等于pivot的两部分然后对两边递归排序。快速选择只需要关心一侧如果pivot最终落到了我们要找的位置直接返回如果目标在左侧就只递归左侧如果目标在右侧就只递归右侧。另一侧完全不用管。正因为每次只需要处理一半的数据它的平均时间复杂度从快排的O(n log n)降到了O(n)。快速排序是“两边都要管”快速选择是“只管一边”这就是全部区别。4.2 partition分区函数的稳定实现先写一个标准的Lomuto分区原地重排数组返回pivot最终所在下标int partition(vectorint nums, int left, int right) { int pivot nums[right]; // 每次取最右边的元素作为基准 int i left - 1; // i指向最后一个“小于等于pivot”的位置 for (int j left; j right; j) { if (nums[j] pivot) { i; swap(nums[i], nums[j]); } } swap(nums[i 1], nums[right]); return i 1; }这里有个容易写错的地方i的初始值是left - 1不是0。因为分区函数可能会处理子数组而不是整个数组。如果你图省事写成int i 0那在递归到右半部分时分区逻辑会完全错乱。这个bug肉眼不好查跑起来数据一大就崩我见过不止一个同学卡死在这里。另一个常见错误是写成。如果你只让严格小于pivot的元素放到左边那等于pivot的元素会被堆到右边在大量重复元素的场景下分区会严重失衡递归退化。4.3 递归方向的判定与代码实现拿到分区函数之后整个快速选择的核心逻辑就是判断“要找的位置在分区的哪一侧”。这里我提供一个减少思维负担的写法把“第K大”统一转换成“第n - K 1小”然后求该位置的元素。转换成“第index小”之后递归方向的判断就变得特别直观如果pivot的最终下标等于index - 1说明pivot恰好就是我们要找的第index小元素直接返回如果pivot下标小于目标位置去右边找否则去左边找。class Solution { public: int findKthLargest(vectorint nums, int k) { int index nums.size() - k; // 第k大 → 第 (n-k1) 小 → 下标 n-k int left 0, right nums.size() - 1; while (left right) { int pivotIdx partition(nums, left, right); if (pivotIdx index) { return nums[pivotIdx]; } else if (pivotIdx index) { left pivotIdx 1; // 目标在右侧 } else { right pivotIdx - 1; // 目标在左侧 } } return -1; // 理论上不会走到这里 } };递归写法会更简洁但我个人更喜欢用while循环。为什么因为递归版本每递归一次都要重新拷贝边界参数栈深度在极限情况下可能到达O(n)而while循环完全避免了这个问题。面试时写循环版本还能顺带展示你对“递归转迭代”的理解。4.4 平均O(n)的来源与最坏情况兜底很多人背下来了“快速选择平均O(n)”但被问到“为什么最坏会变成O(n²)”就答不上来。这里解释一下。快速选择每次partition后期望只处理一半的数据。如果每次都能把数组差不多对半分那么总工作量是n n/2 n/4 ... 2n所以平均是O(n)。但如果你运气差每次pivot都选到了当前区间的最小值或最大值分区后左右两边极不平衡每次只能去掉一个元素那总工作量就是n (n-1) (n-2) ... O(n²)。避免退化有几种手段按实用程度排序随机选pivot每次从[left, right]随机取一个下标和nums[right]交换让最坏情况变成概率意义上的几乎不可能。这是工程上最推荐的方案实现成本最低。三数取中取左、中、右三个位置的中间值作为pivot能有效避免近似有序数组的退化。BFPRT算法中位数的中位数理论上能把最坏情况降到严格O(n)但常数巨大竞赛里都不太用面试时能说出来名字、解释思路就够了。我建议在笔试里直接用随机选pivot版。曾经有个同学用固定取右端点的版本去跑大规模近乎有序的测试数据直接超时换成随机pivot后一遍过。这种性能差异不是代码逻辑错误纯粹是pivot选择策略的问题。5. 实战踩坑超时、越界、死循环排查实录5.1 排序后索引算错——第K大不等于下标K有个使用排序解法常见的错误写了return nums[k]自己在本地用小数组测试时发现输出好像“差不多对”但一旦k恰好等于n就越界。第K大在下标上永远要记得“从1开始计数”和“数组从0开始计数”的错位。k1时应该是数组中最大值对应升序下标的n-1也就是n-k。kn时对应最小值升序下标0依然满足n-k 0。所以n-k这个公式在所有情况下都是自洽的。如果你非要用降序下标那就是k-1。这两个公式可以互相验证建议写在草稿纸上别靠心算。5.2 快速选择进死循环——分区边界没锁死快速选择一个隐蔽的坑是left pivotIdx 1和right pivotIdx - 1这两个更新语句看起来不起眼但缺一个或者写错一个程序就会陷入死循环。举个例子如果目标位置在左侧你写成left pivotIdx而不是pivotIdx - 1而pivot恰好又在目标右侧那下一轮partition的时候区间的左边界根本没变pivot还是同一个结果还是同一个无限循环。这个bug的可怕之处在于它不会立刻报错只是让程序卡住不动新手很难第一时间联想到是边界更新错了。排查技巧在while循环里打印每次的left、right和pivotIdx如果发现连续两次输出一模一样说明边界更新有问题沿着这个方向查准没错。5.3 重复元素导致分区失衡——pivot选择的处理如果数组里全是重复元素比如[5,5,5,5,5]取最右端pivot进行分区时的比较会让所有元素都跑到左边去partition返回的下标是right - 1。此时右侧区间为空递归方向判断会变得非常极端。这是快速选择在工程应用中一个真实的痛点。处理方式一般有两种换用双指针的双向分区Hoare分区让等于pivot的元素尽量均匀分布在两侧。保持Lomuto分区但配合随机pivot让重复元素导致的失衡在概率上被抹平。我个人的建议是笔试面试里优先使用随机pivot Lomuto分区代码短、思路清晰、重复元素场景下表现已经足够好。双指针分区虽然更稳但写错的概率也更高如果不是特别熟练不要在高压环境下临场尝试新写法。5.4 手写堆与标准库优先队列的选择有些学校作业或比赛环境禁用标准库容器逼着你手写堆。手写堆时最容易错的是“上浮/下沉”操作的边界条件下沉操作中子节点下标不能越界要判断child 1 heapSize是否存在右孩子。上浮操作中要确保当前节点不是根节点idx 0才能跟父节点比较。比较方向容易搞反求第K大我们维护的是小顶堆堆顶是“当前最大的K个里最小的”所以新元素比堆顶大才入堆不是比堆顶小入堆。如果允许用标准库我强烈建议直接用priority_queue或heapq。因为笔试环境拼的就是速度和准确率标准库堆经过无数人验证比自己手写的稳得多。手写堆可以作为理解原理的练习但没必要在限时场景里给自己加难度。6. 解法选型与TopK问题扩展6.1 面试时的回答节奏和代码风格建议面试回答这题时一个稳妥的叙述顺序是先排序再堆最后快速选择。每一步都主动交代复杂度并说明为什么下一步更优。这样既展示了基础扎实又展示了优化意识。举个标准的回答节奏“最先想到排序O(n log n)简单直接。但我们可以用大小为k的小顶堆把复杂度降到O(n log k)空间O(k)适合处理流式数据。如果数组已经全部加载在内存里且k很小或k很接近n堆的空间和操作都不划算用快速选择可以做到期望O(n)只需要O(1)的额外空间。”这段话本身就值很多分因为它体现了数据规模意识。代码风格上我建议变量名在保持简洁的前提下尽量要有含义别用a、b、c。面试官看你代码的时间可能比你写代码的时间还长清晰的命名就是在帮对方省时间。6.2 从215延伸出去的TopK变形题把215题的思路迁移开你会发现一大批题目其实在考同一个能力数据流中的第K大元素维护一个固定大小K的小顶堆每来一个新元素就走一遍“比堆顶大就替换”的逻辑。和215的区别就是数据不是一次性给出的而是源源不断来的。前K个高频元素先用哈希表统计频率再建立一个“按频率比较”的小顶堆堆里始终保存频率最高的K个。有序矩阵中的第K小元素可以利用堆来做多路归并也可以二分答案后用计数判断。里面二分答案的思路本质上也是一种“快速选择”思想的变体。数据流中的中位数维护一个最大堆和一个最小堆两堆大小相差不超过1中位数就是堆顶之一。这是215题堆解法的直接升级版面试出现频率也非常高。把这些题放在一起刷你会发现规律极其明显凡是要“第K”的先想能不能用堆凡是要“最值中的第K”的再想能不能做二分答案或快速选择。最后分享一个我个人的刷题习惯215题我前后写过不下十遍每次换一种语言、换一种分区写法、换一种堆的实现方式。直到有一次在闲聊时被问到“你有想过为什么快速选择的期望复杂度是O(n)而不是O(n/2)吗”我才意识到其实不少人连这个结论的来龙去脉都说不清。如果你也只能背结论建议现在就把快速选择的推导过程亲手写一遍——有些东西刷一遍不如手推一遍记得牢。这题就像一把万能钥匙真正掌握后TopK这一类问题对你来说就再也不会是难题了。
排查实战：磁盘告警背后的隐形写入与优化)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
