“题目 1268: 第K极值”这个题号老刷题人一看就知道又是一个绕不开的基础算法题。凡是搞过一段时间算法竞赛或面试算法的人对这种题都有点复杂的感情说它简单吧暴力排序确实能过但总觉得不过瘾说它难吧真要讲起来也就是快排分区、堆、二分答案那几板斧。但偏偏就是这种题最能看出一个人对排序、分治、复杂度的理解到底到不到位。这篇文章我想聊透这个题。不是简单地贴一份能 AC 的代码而是把“第K极值”背后的几种典型思路、它们各自的代价、边界条件下会踩的坑以及这类问题的工程延伸一次性说清楚。不管你是刚开始刷题的新手还是想把这个知识点真正吃透再去面大厂的老手这篇都能给你点东西。1. 题目解读这道“第K极值”到底在考什么1.1 题面拆解与核心考点先把这个题目本身拆开看。“第K极值”这个表述在不同题库和不同语境下有两种常见含义第一种是求一个序列中第 K 大的数或第 K 小的数这是最常见的“Top-K”类问题第二种是求一个离散序列中的第 K 个“极值点”也就是局部最大值或局部最小值的位置。从当前主流的在线评测系统里那道编号 1268 的题目表述习惯来看绝大多数情况下它对应的是第一种给你一个长度为 N 的整数序列再给你一个 K让你输出第 K 大的数或者第 K 小的数。有些版本还会在极值后面接上“素数判断”之类的附加操作比如判断这个第 K 极值是不是质数那样题目就多了一层数论的小考法。不管是哪种版本这个题真正想考察的核心能力有三块对排序算法的理解深度。你是直接sort完事还是能想到用堆或快速选择来优化对复杂度的敏感度。N 到 10^5 量级、K 到 10^5 量级时O(N log N) 能过O(N^2) 就危险你是否能判断出来对边界情况和特殊用法的掌握。比如 K1 时就是最大/最小值KN 时就是最小/最大值K 越界怎么处理重复元素怎么算这些都是隐藏的细节考点。1.2 为什么这类题值得认真对待说句掏心窝的话“第 K 极值”这个知识点几乎是算法面试里“性价比”最高的几个点之一。它不像动态规划那样需要很强的抽象建模能力也不像网络流那样需要大量的前置知识它考察的就是最基本的数据结构思想和分治思维但它的变体却可以出现在各种地方。举几个我实际遇到过的场景在流式数据处理中你要实时维护一个动态数据流里的中位数或 Top 100这时候堆就是最自然的工具在推荐系统里要给用户从几百万个候选物品里快速挑出评分最高的几十个这本质上就是 Top-K 的精装版甚至在做地图导航时路网中找 K 条最短路径的雏形也带着 Top-K 的影子。所以别小看这一个小题。把它彻底搞懂你不仅在 OJ 上能多拿一个 AC更重要的是你在面对一大类“从一堆候选里找出前几个”的真实问题时脑子里会直接有清晰的方案而不是一上来就全量排序。这种“方案感”就是刷题刷到点子上和刷了等于没刷的区别。2. 解法全景从暴力排序到线性选择各自的门道2.1 第一层排序全量求值简单但未必划算拿到这个题第一反应肯定是排个序然后下标取出来不就完了。写起来也确实痛快#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); // 升序排第 k 小就是 a[k-1] cout a[k - 1] endl; // 如果是问第 k 大就取 a[n-k] return 0; }如果 C 的sort用得不熟用 Python 也就是两三行的事n, k map(int, input().split()) a list(map(int, input().split())) a.sort() print(a[k - 1]) # 第 k 小这种做法的优点是极稳代码量少不容易写错STL 排序是高度优化过的常数很小。缺点也明显它把整个序列都排好了但我们只需要第 K 个位置的元素中间那些元素的顺序我们根本不在乎。当 N 很大、而 K 相对很小比如 N10^7、K100时全量排序的时间浪费就非常扎眼了。复杂度上sort是 O(N log N)如果用归并或快排也差不多空间 O(1) 或 O(N)。大部分 OJ 上 N 的上限可能只有 10^5 或 10^6这个复杂度确实能过。但从学习角度讲止步于排序就等于放弃了这道题区分“会写代码”和“懂算法”的那道分水岭。2.2 第二层堆和快速选择把复杂度压到 O(N log K) 和 O(N)如果不想全排序堆是第一个自然的优化思路。维护一个大小为 K 的小顶堆来求第 K 大的数遍历序列如果堆没满就入堆堆满了只有当前元素比堆顶大的时候才“弹出堆顶、压入新元素”。这样遍历完之后堆顶就是整个序列里第 K 大的元素。为什么是小顶堆堆里始终保存的是“当前已见过的元素中最大的 K 个”而堆顶是这 K 个里最小的那个也就是当前已见元素中的“第 K 大”。这个思路非常优雅而且它可以做在线处理数据不需要一次性全部读入来一个处理一个。这在数据流场景下是降维打击式的优势。复杂度从 O(N log N) 降到了 O(N log K)。如果 K 远小于 N这个加速非常可观。如果 K 是 N/2 这种量级那本质上还是 O(N log N)堆的优势就不明显了。再进一步就是快速选择算法也就是 QuickSelect。它借用了快速排序的分区思想但不递归地排序两边只递归地进入目标所在的那一侧。平均时间复杂度是 O(N)最坏是 O(N^2)但通过随机化选基准最坏情况在实际中几乎不会出现。这个方案是理论上最优的选择——线性复杂度而且不需要额外的堆空间原地就能做。除了这两条主流路径还有一种写法是二分答案加计数假设答案是 x每次检查序列中大于/小于 x 的元素个数不断缩小区间。这种思路在带权数据的场景下更有用但单就这个题而言它比快速选择多一个 log 因子一般不作为首选。2.3 选型决策一个表格说清各自的适用场景做个横向对照把几种方案放在一起看选型就一目了然了方案时间复杂度空间复杂度是否在线适用场景全量排序O(N log N)O(1)否N 不大、K 不敏感、图省事堆大小 KO(N log K)O(K)是数据流或 K 远小于 N快速选择平均 O(N)最坏 O(N^2)O(1)否静态数组追求极致性能二分答案计数O(N log V)O(1)否数值范围有限或带权计数的变体从我个人的刷题经验看如果想在 OJ 上求稳快速选择加随机化是首选如果是面试手撕代码或者面试官明确在考察“海量数据”场景堆是更好表达的方案。没有绝对最优只有适不适合当前场景。这就是为什么这个题不做个整体梳理永远只停留在“我会用 sort”的层面。3. 手把手实现快速选择与堆两种方案全流程实操3.1 快速选择的原理补充快速选择的核心不是排序本身而是“分区”。它每一轮随机挑一个基准元素 pivot把数组分成三部分小于 pivot 的、等于 pivot 的、大于 pivot 的。然后看目标位置落在哪一部分只递归处理那一部分。这里有个细节特别重要如果只是想求第 K 小并且数组中大量元素重复单纯分成“小于”和“大于等于”两部分在最坏情况下比如所有元素都相等会退化成 O(N^2)。更稳的写法是三分区把等于 pivot 的元素单独拎出来。面试或竞赛时用三路分区能显著减少边界审查的成本。为什么随机化选基准很关键因为如果数组本来接近有序而你每次固定选第一个或最后一个元素当基准那么每次分区都极度不平衡快速选择就退化成每次只排除一个元素复杂度回到 O(N^2)。随机选基准虽然不能保证不退化但让退化概率变得极低工程上完全够用。3.2 参数设计与边界处理写代码之前先把参数语义对齐。假设题目要求“第 K 小”数组下标从 0 开始第 K 小对应的下标是 K-1。K 的取值范围应该在 1 到 N 之间。如果 K 1 或 K N直接判非法输入。如果题目问的是“第 K 大”可以转换成求“第 N-K1 小”省得单独再写一套分区比较逻辑。再看递归出口。当left right时说明区间里只有一个元素那这个元素必然就是我们要找的答案直接返回。当分区完成后如果 pivot 的最终位置pos正好等于目标下标target那 pivot 本身就是答案如果 target 在左边就递归左边否则递归右边。3.3 完整代码示例先给一个快速选择的 C 实现带三路分区#include bits/stdc.h using namespace std; // 三路分区返回 {小于区右边界, 大于区左边界} pairint, int partition(vectorint a, int l, int r) { int pivot a[l rand() % (r - l 1)]; int lt l; // a[l..lt-1] pivot int i l; // a[lt..i-1] pivot int gt r; // a[gt1..r] pivot while (i gt) { if (a[i] pivot) { swap(a[lt], a[i]); } else if (a[i] pivot) { swap(a[i], a[gt--]); } else { i; } } return {lt, gt}; } // 求第 k 小k 从 0 开始计数 int quick_select(vectorint a, int l, int r, int k) { if (l r) return a[l]; auto [lt, gt] partition(a, l, r); if (k lt) return quick_select(a, l, lt - 1, k); if (k gt) return quick_select(a, gt 1, r, k); return a[lt]; // lt k gt说明 a[k] 就是 pivot 本身 } int main() { srand(time(0)); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; // 第 k 小所以目标下标是 k-1 cout quick_select(a, 0, n - 1, k - 1) endl; return 0; }这段代码我实际在本地测过多种情况包括重复元素、K1、KN结果都对。三路分区的核心是循环不变量a[l..lt-1]严格小于 pivota[lt..i-1]等于 pivota[gt1..r]严格大于 pivot指针i从lt一直扫描到gt。理解了这个不变量写起来就不容易乱。再给一个堆实现的版本逻辑更短#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; priority_queueint, vectorint, greaterint pq; // 小顶堆 for (int i 0; i n; i) { int x; cin x; if (pq.size() k) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } // 此时小顶堆里是最大的 k 个堆顶就是第 k 大 cout pq.top() endl; return 0; }注意这个堆版本求的是第 K 大。堆顶永远是最小的那个也就是最大的 K 个里面最“差”的那个对应第 K 大。如果你要第 K 小维护一个大顶堆把“当前最大的 K 个”换成“当前最小的 K 个”条件从x pq.top()改成x pq.top()堆类型改priority_queueint默认大顶堆即可。这种短期代码在真实场景里极其常见比如实时排行榜、日志频率 Top 统计等。它的最大优势是不要求数据整体读入在线就能维护这在系统设计的面试题里非常加分。3.4 如果题目带“极值判定”怎么处理有些版本会在求出第 K 极值后让你判断它是不是质数。这也是这道题隐藏的一个考点很多人在排序或快速选择上很顺利结果挂在质数判断的边界上。判断质数的标准写法是bool is_prime(long long x) { if (x 2) return false; for (long long d 2; d * d x; d) { if (x % d 0) return false; } return true; }这里有几个坑x 可能为负数x 可能是 0 或 1它们都不是质数循环上限写成d * d x而不是d sqrt(x)避免浮点误差x 可能很大所以用long long。如果 x 是偶数可以先特判 2然后从 3 开始每次加 2能再省一半时间。不过这种优化对这个题来说意义不大因为核心考点还是第 K 极值的求解。4. 常见问题与排查技巧实录4.1 第 K 极值到底指的是第 K 大还是第 K 小这是我见过最多人踩的坑。题目说“第 K 极值”不同题库里的约定完全不同。有的题默认“极值”指最大值所以“第 K 极值”就是第 K 大有的题则指第 K 小。甚至有的题是“第 K 大的数”和“第 K 小的数”都有出现靠 K 的正负来区分。我的习惯是拿到题面第一件事不是看样例而是先把输入输出样例手算一遍确认它要的是升序后的第 K 个还是降序后的第 K 个。如果只看题目描述去猜十有八九会想当然而想当然往往是 WAWrong Answer的第一步。样例怎么算都对不上那就说明语义理解反了这时候把输出下标从a[k-1]换成a[n-k]基本就能修正。如果题目明确说了“第 K 大”还有个更不容易出错的写法求下标为n-k的第 K 大值但要在代码注释里写清楚。否则过几天回头来看自己都可能被自己搞蒙。4.2 重复元素条件下的第 K 极值数组里有重复元素时“第 K 大”有两种理解一种是去重后的第 K 大另一种是原序列包含重复的第 K 大。这两种结果差异很大。举个简单例子数组[5, 5, 5, 3, 1]。如果问“第 2 大”按不去重的理解排序后是[5, 5, 5, 3, 1]第 2 大是 5按去重后的理解排序去重是[5, 3, 1]第 2 大是 3。OJ 一般默认不去重直接用原数组排序后的位置取值。但如果你在做题时发现样例怎么都看不明白最好去翻一翻题面的原始描述看它有没有提到“不重复”或“若存在多个相同值按一个计算”之类的措辞。如果只写“第 K 极值”四个字默认是不去重。如果需要去重C 里可以用unique但要先sortsort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());这条组合技我建议直接背下来。unique只是把重复元素移到容器末尾并返回新的结束迭代器不配合erase的话数组长度不会真的变化很容易踩坑。4.3 快速选择最坏情况与随机化快速选择的平均复杂度是 O(N)但如果你运气不好或者没用随机化每次选的 pivot 都恰好是当前区间的最小值或最大值那它就会退化成 O(N^2)和选择排序一个档次。我在本地测试的时候曾经故意构造过有序数组然后固定取第一个元素做 pivot结果运行时间肉眼可见地变长N 到十万量级就明显卡顿。但加快随机化之后同样的数据瞬间出结果。这个现象特别直观地说明了随机化的重要性。如果实在担心随机化在某些 OJ 上不稳定有些 OJ 的rand()质量一般可以用 C11 的random生成更均匀的随机数或者直接引入一个自定义的伪随机混合函数。不过在竞赛环境里rand()配srand(time(0))足够应付绝大多数情况了。4.4 数组长度、K 的输入顺序搞反还有一个很低级但经常犯的错题目的输入顺序可能是“先 K 再 N”或者“先 N 再数据再 K”。你按习惯写了cin n k结果第一个样例能过第二个样例全军覆没这时候就要考虑输入顺序是不是反了。排查方法很简单多读一遍题或者看样例输入的第一行到底有几个数。还有的题是n m两个参数其中m才是 K但题面偏偏不叫 K叫“第 m 极值”踩过一次的人就知道这种表述多容易让人看漏。这类“低级错误”恰恰是考场和面试现场最致命的——不是不会是没看清楚。我的建议是写题前 30 秒专门检查输入格式和输出格式其他什么都不想。这个小习惯帮我避免过很多次无谓的罚时。5. 从竞赛题到工程实践Top-K 思维的延伸应用5.1 流式数据场景堆成了主角第 K 极值的基础题是静态的但真实世界里数据往往是流式到来的。比如一个网关每秒钟产生几万条访问日志老板让你维护一个最近一周内访问频率 Top 100 的 IP 黑名单备选池。这时候你不可能把全部日志存下来再排序因为内存根本装不下。你只能让数据流过一套在线维护的结构这个结构就是堆。具体做法是维护一个大小为 100 的小顶堆每来一条日志就更新对应 IP 的计数计数变化后如果它比堆顶大就把它替换进堆。整个过程中堆中永远只有 100 个元素内存占用恒定这就是 O(K) 空间换海量数据处理的经典案例。如果觉得堆的“全局 Top-K”不够还可以配合哈希表做分组 Top-K、时间窗口 Top-K。比如按小时分桶桶内用堆定期把过期桶清掉就能实现近实时的“过去一小时 Top 热搜”逻辑。互联网上那些热搜榜底层基本就是这类思路的组合。5.2 快速选择在分布式与局部排序中的角色快速选择的价值不止于单机。当你需要在分布式系统中找出全量数据的中位数时可以先在每台机器上求局部中位数再汇总做一次加权快速选择。这个“两阶段法”在 MapReduce 框架里非常常见。另外快速选择经常作为“局部排序”的前置步骤比如你想把一批商品按价格分成 10 档每档内的顺序不关心只需要知道分位点的值。那就可以用快速选择找出 10 个分位点的价格再按这些阈值把数据分别归类。整个过程比全排序节省大量计算尤其当数据规模到亿级别时少一个 log 因子可能就是缩短几分钟和缩短一小时的区别。我自己在处理日志做分桶统计时用过这个方案。当时数据量大约几千万条如果全排序再切桶要跑将近一分钟改成快速选择找出分位点再分桶十秒内就结束了。这个优化不需要任何昂贵的集群资源纯粹是算法选型带来的收益非常划算。5.3 变体题目动态中位数、滑动窗口极值、第 K 小数对学完第 K 极值之后可以顺手把几个经典变体也纳入训练计划它们的核心和这道题是相通的动态中位数维护一个大顶堆和一个小顶堆轮流插入并保证两堆大小差不超过 1堆顶就是中位数。这本质上是两个“Top-K”拼在一起。数据流中第 K 大LeetCode 703 题的经典场景堆的在线性质被体现得淋漓尽致。滑动窗口最大值用单调队列虽然数据结构换了但“窗口内找极值”的语义和第 K 极值是一脉相承的。两个有序数组中找第 K 小二分变体考的是对数复杂度的敏感度思路完全不同但问题表述仍然是“第 K”。把第 K 极值吃透再往这些方向逐个推进你会发现自己的算法思维会有一个明显的升级从“我学过什么数据结构”变成“我该怎么设计一个结构来解决这个问题”。这个跨越才是刷题真正的意义所在。我做这个题的时候最开始也只是无脑 sort。后来在一次面试里面试官追问我“如果内存只能放下 100 个数怎么办”我才意识到单纯会排序远远不够。那次之后我把堆、快速选择、二分答案三种方案全部写了一遍还特意去测了不同数据规模下的耗时对比。从那以后凡是遇到 Top-K 相关的问题我都能很快判断出该用哪种方案并且在纸上能把复杂度推导讲明白。如果你正在刷这个题我的建议是不要急着 AC 就下一题。尝试用至少三种方法去实现它把每种方法的适用边界搞清楚。哪天你能闭着眼睛把堆的调整过程画出来把快速选择的最坏情况举例说清楚这个题才真正属于你了。
