企业官网建设流程全解析

“题目 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) 就危险，你是否能判断出来？
• 对边界情况和特殊用法的掌握。比如 K=1 时就是最大/最小值，K=N 时就是最小/最大值，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; vector<int> 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 相对很小（比如 N=10^7、K=100）时，全量排序的时间浪费就非常扎眼了。

复杂度上，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 选型决策：一个表格说清各自的适用场景

做个横向对照，把几种方案放在一起看，选型就一目了然了：

从我个人的刷题经验看，如果想在 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-K+1 小”，省得单独再写一套分区比较逻辑。

再看递归出口。当left == right时，说明区间里只有一个元素，那这个元素必然就是我们要找的答案，直接返回。当分区完成后，如果 pivot 的最终位置pos正好等于目标下标target，那 pivot 本身就是答案；如果 target 在左边，就递归左边；否则递归右边。

3.3 完整代码示例

先给一个快速选择的 C++ 实现，带三路分区：

#include <bits/stdc++.h> using namespace std; // 三路分区：返回 {小于区右边界, 大于区左边界} pair<int, int> partition(vector<int>& 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[gt+1..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(vector<int>& 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; vector<int> 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; }

这段代码我实际在本地测过多种情况，包括重复元素、K=1、K=N，结果都对。三路分区的核心是循环不变量：a[l..lt-1]严格小于 pivot，a[lt..i-1]等于 pivot，a[gt+1..r]严格大于 pivot，指针i从lt一直扫描到gt。理解了这个不变量，写起来就不容易乱。

再给一个堆实现的版本，逻辑更短：

#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; priority_queue<int, vector<int>, greater<int>> 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_queue<int>默认大顶堆即可。

这种短期代码在真实场景里极其常见，比如实时排行榜、日志频率 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 个。如果只看题目描述去猜，十有八九会想当然，而想当然往往是 WA（Wrong 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，但要先sort：

sort(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()质量一般），可以用 C++11 的<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 就下一题。尝试用至少三种方法去实现它，把每种方法的适用边界搞清楚。哪天你能闭着眼睛把堆的调整过程画出来，把快速选择的最坏情况举例说清楚，这个题才真正属于你了。