“谁考了第k名”是我见过不少入门算法题合集里都有的老朋友。光看标题会以为这就是个排序题学生信息排个序输出第k个但真正动手做的人十有八九会在边界条件、并列名次、索引偏移上翻车。我当年第一次提交就挂在了“成绩相同怎么排名”这个业务细节上后来带新人时发现大家踩的坑几乎一模一样。这篇文章就把这个题目掰开揉碎从题目拆解、算法选型、代码实现到排查经验完整过一遍适合刚学完排序和结构体、准备刷题入门的人也适合那些想从“暴力排序”升级到“快速选择”的老手。1. 题目背后到底在考什么1.1 从“谁考了第k名”到Top-K问题这个题的标准描述通常长这样给出n个学生的学号和成绩按成绩从高到低排名然后回答“第k名是谁成绩是多少”。看起来只是排序后按下标取数但它的本质其实是数据结构与算法里的Top-K问题家族。Top-K问题有两个经典分支一个是“求前K大/前K小”另一个是“求第K大/第K小”。前者要输出一批元素后者只需要一个确定位置的值。“谁考了第k名”属于后者但在很多变体题里可能要求输出前k名的完整名单那又回到了前者的范畴。判断一道题到底在考什么不能只看题目问法还要看数据范围。如果n只有100冒泡排序都能过如果n是10的5次方量级O(n log n)的全排序依然能过如果n到了10的7次方量级内存和时间都开始吃紧全排序就显得笨重这时候就能引出快速选择算法或堆方案。很多刷题平台给的隐藏测试点恰恰就是大数据量所以只写一个sort然后交上去可能会卡在时间限制上。我在实际面试中也遇到过类似场景面试官不是真的关心你能不能调出排序函数而是想看看你懂不懂“全排序是奢侈的”这个道理。理解这个问题背后的知识脉络很重要。它向下连接排序算法、比较器设计、稳定性规则向上延伸到分治思想、堆结构、随机化算法。如果你只把这道题当成“写个sort交差”那你损失了这个题目至少一半的价值。我见过有人把这个题做完后顺手把Top-K家族的问题全部串了起来后面再遇到“求数组里第k大的数”“求流数据中位数”这类题时明显游刃有余。1.2 一个隐藏的考点并列名次怎么算“谁考了第k名”最经典、也最容易被忽略的坑是并列名次的处理。很多人在写排序比较器的时候只比较了成绩字段然后直接按下标输出第k个元素。但第k名的“名次”在不同的业务规则下含义完全不同。第一种规则是“排名允许并列但占位”比如小明和小红都是95分都是第1名那么下一个92分的人就是第3名不存在第2名。这种情况下你问“谁考了第2名”答案是“没有人”或者说查询无结果。第二种规则是“排名允许并列但不占位”也就是常说的“并列后顺延”95分并列第192分直接视为第2名此时第2名就是92分的那位同学。第三种规则更简单就是完全忽略并列硬性按排序后的顺序编号那只管输出排序后第k个位置的人就行这种情况本质上是“第k个高分”而不是真正的“第k名”。题目描述里如果写了“分数相同则按学号升序排列”那通常意味着出题人采用了第三种规则也就是先把人排好再按序号取数。如果描述里写了“名次并列”或“成绩相同则名次相同”你必须在输出前单独计算名次。这个差异直接决定代码逻辑甚至决定你写的排序函数有没有意义。我在实际做这类题时会先把题目里的排名规则用一句话写死在注释里避免写代码写着写着就忘掉了业务语义。还有一层隐藏考点当成绩相同时排序结果是否稳定。比如同样90分学号是1001的同学和学号是1002的同学如果题目要求学号小的排前面你必须在比较器里同时比较学号和成绩不能依赖sort的稳定性。C里的std::sort是不稳定排序Java的Collections.sort是稳定排序Python的sorted也是稳定排序但如果你在自定义比较器里只写了成绩字段那“稳定”这个特性根本不会被触发最终同分学生的相对顺序就是未定义的。这是非常典型的“语言特性陷阱”。2. 最稳妥的方案排序后再取数2.1 结构体排序的关键设计对于这个题目来说最直白的做法就是把每个学生的信息封装成结构体或类然后按成绩排序。以C为例定义结构体时要在意内存布局和字段顺序。一般写成这样struct Student { string id; // 学号 int score; // 成绩 };如果题目保证学号是纯数字用string还是long long我建议能用数字就用数字。因为学号有时候会有前导零比如“000123”一旦用long long存储前导零就丢了输出时还得补零。所以稳妥起见学号用string存储排序时按业务规则决定是否用string排序。这看起来是个很小的细节但我在实际判卷中发现不少同学输出了“123”而不是“000123”白白丢分。结构体设计的原则是“只放必要字段”。有的同学喜欢额外加一个rank字段想先把名次算好存起来。这个思路不坏但如果后续排序规则变化或者数据被洗牌rank字段就可能变成脏数据。更好的做法是结构体里只放原始信息名次在输出时按规则计算。如果你确实想在一次排序后把名次填进去那就再用一个单独的循环处理不要一边排序一边填名次。比较器的写法是这个方案里最核心的部分。C可以这样写bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; }这段逻辑的意思是成绩不同时分数高的排前面分数相同时学号小的排前面。为什么要写成这样而不是只写return a.score b.score因为我们需要让同分学生的顺序可预期。你可能会说如果题目没有要求同分按学号排列那是不是就可以不写第二行从功能角度确实可以但从可复现性角度我强烈建议还是写完整。你永远不知道测试数据里有没有同分的情况写完整比较器能保证结果稳定也方便后续改需求。2.2 排序稳定性与成绩相同时的排序规则排序稳定性是个经常被忽略、但一旦踩坑就非常难受的概念。稳定排序的意思是如果两个元素的关键字相等排序后它们的相对顺序保持不变。C的std::sort不是稳定排序这意味着当你的比较器只按成绩比较时两个同分学生谁前谁后是不确定的具体结果取决于算法内部的划分和数据的原始顺序。如果题目要求“同分时保持输入顺序”那你不应该依赖std::sort而应该使用std::stable_sort或者干脆在比较器里加上一个唯一的次要关键字。我记得有一次我处理一个真实榜单需求数据库查出来的数据已经按某个字段有序我想在前端再按成绩排序一次结果用了不稳定排序后相同成绩的名单顺序乱了用户反馈“榜单跳动”排查了半天才发现是排序稳定性问题。从那以后我写比较器时一定会检查是否需要保留原顺序。用stable_sort的成本通常比sort稍高因为稳定排序通常需要额外的内存空间来归并或者采用更复杂的算法策略。在刷题场景里如果n在10的5次方量级性能差距可以忽略如果n很大且你又不关心同分顺序那直接用sort也无可厚非。关键是你要“知道自己在做什么”而不是碰运气。还有一种特殊需求是“按名次排序”而名次可能相同。比如两个人都考了95分并列第1那么它们应该怎么排序这跟前文说的“第k名”的定义是强相关的。如果榜单只需要展示人的顺序那并列名次的人随便谁先谁后都行如果需要稳定展示通常会再按学号、姓名之类的字段作为第二排序键。我在项目里处理过这种需求最后的方案是先排序计算名次再按名次加第二关键字排序。两步排序虽然多了一次遍历胜在逻辑清晰。2.3 输入输出细节与边界条件这个题目的输入格式一般是先给n和k再给n行“学号 成绩”。我在解析输入时有个习惯先读完整行再按空格拆分而不是用流式提取。虽然流式提取简单但一旦遇到成绩是浮点数、学号带有奇怪前缀、或者行尾有多余空格的情况流式操作就会出问题。用getline配合字符串拆分更稳代价是麻烦一点。刷题平台的数据通常比较规范但“规范数据”不意味着没有前导空格或换行符。边界条件方面至少要考虑这几种情况k1取最高分必须正常输出。kn取最低分排序后取最后一个元素索引是n-1。n1, k1只有一个学生这是最容易测出越界错误的场景。所有学生成绩相同你的排序结果是否稳定排名规则是否明确。存在负数成绩或0分如果成绩用int存负数是合法输入输出时要正确处理。学号可能很长用string存不要用int。输出时要注意格式。很多题目要求输出“学号 成绩”中间可能有一个空格也可能有多个行尾是否允许换行。我一般输出成cout stu[k-1].id stu[k-1].score endl;。这里最关键的是索引偏移排序后第1名在下标0第k名在下标k-1。这种“第k名对应下标k-1”的映射新手经常搞错一错就是“差一错误”。差一错误是这个题目最高频的bug没有之一。我在测试自己的代码时会用一个小数据集手推一遍然后专门把k设为1和n各测一次。这两组数据能把90%的索引错误暴露出来。3. 数据量一大排序就不够聪明了3.1 快速选择算法只关心第k名全排序的时间复杂度是O(n log n)但如果你只需要第k名理论上可以把复杂度压到平均O(n)。这就引出了快速选择算法。快速选择的内核与快速排序相同选一个基准把数组分成左边比基准大、右边比基准小然后判断第k个元素落在哪个区间只递归处理那一侧。以“成绩从高到低排名且第k名”为例每次partition后基准元素的下标p会把数组分成两部分。如果p正好等于k-1那基准元素就是第k名如果p大于k-1第k名只可能在左半部分如果p小于k-1则在右半部分。这样每次递归只处理一个子区间平均复杂度就降到了O(n)。快速选择最怕什么最怕基准选得不好退化成O(n^2)。比如原始数据本来就有序而你每次选第一个元素做基准那partition完一边空一边全是数据递归深度变成n直接退化成最坏情况。解决办法有两个一是随机选择基准二是使用“三数取中”策略取左端、右端、中间三个数的中位数作为基准。刷题时为了省事最常用的是随机基准。在C里可以用rand()或mt19937生成随机下标Python里可以用random.randint。我建议真正想把这个算法掌握扎实的人手动实现一遍而不是调用nth_element。C标准库提供了std::nth_element它能在线性时间内把第k大的元素放到正确位置而且比你自己写的快速选择经过了更多优化。但刷题和面试的时候如果你只是背了一个函数名面试官继续追问“你了解实现原理吗”的时候你就傻眼了。所以我的建议是先手写一遍快速选择理解了分区逻辑再去用库函数节省时间。3.2 堆方案处理动态Top-K另一个经典思路是使用堆。对于“求第k大”的问题维护一个大小为k的最小堆遍历所有成绩如果堆不满k个就直接入堆如果堆满了当新元素大于堆顶即当前第k大的值就弹出堆顶、压入新元素。遍历结束后堆顶就是第k大的元素。为什么用最小堆而不是最大堆因为我们需要随时知道“当前第k大的门槛”是多少堆顶就是那个门槛。如果新元素连门槛都过不了那它一定不在前k大里。如果你用最大堆来存所有n个元素再逐个弹出k次那时间复杂度是O(n log n)跟排序没有本质区别还浪费了堆的空间优势。最小堆方案的时间和空间复杂度分别是O(n log k)和O(k)。堆方案的另一个巨大优势是可以处理动态数据流。如果数据是实时到达的你没法等数据全部收集完再排序。这时候维护一个大小为k的堆简直是标准答案。我记得有一次做实时排行榜功能用户分段提交成绩我用的就是最小堆思路每来一个新成绩就尝试更新前k名单效果很好。但堆方案也有缺点它只能告诉你第k大是谁不方便告诉你完整的前k名名单因为你把堆弹出来会破坏堆。如果你想输出前k名那就得复制堆或者重新组织数据。所以静态数据场景下快速选择通常比堆更直接动态数据场景下堆才是首选。3.3 三种方案对比与选型建议把排序、快速选择、堆三种方案放在一起对比核心维度是时间复杂度、空间复杂度、适用场景和实现难度。方案时间复杂度空间复杂度适用场景实现难度全排序O(n log n)O(1)或O(n)数据量不大需要完整榜单低快速选择平均O(n)最坏O(n^2)O(log n)递归栈静态数据只查第k名中堆O(n log k)O(k)动态数据流维护前k名中选型建议很简单初学阶段先用排序它能帮你快速验证业务逻辑如果数据范围告诉你n很大上快速选择如果数据是动态到达的上堆。不要盲目追求“最优算法”因为算法的常数项、代码正确性和可维护性同样重要。我在实际项目中还遇到过一种场景需要多次查询不同的k。如果每次查询都重新快速选择一遍复杂度很高如果先把数据完整排序那每次查询就是O(1)的索引访问。这种“预处理贵、查询便宜”的取舍也是排序方案的另一个价值。你在考试或面试中如果遇到“多组查询第k名”的变体别急着写快速选择先想想排序是不是更划算。4. 实操过程与核心环节实现4.1 完整实现排序版代码示例我用C写一个完整的排序版本作为对照组方便后面和快速选择版本对比#include bits/stdc.h using namespace std; struct Student { string id; int score; }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; // 同分按学号升序 } int main() { int n, k; cin n k; vectorStudent stu(n); for (int i 0; i n; i) { cin stu[i].id stu[i].score; } sort(stu.begin(), stu.end(), cmp); cout stu[k-1].id stu[k-1].score endl; return 0; }这段代码的核心只有sort加输出但每一行都有讲究。vectorStudent stu(n)提前分配空间避免push_back动态扩容。cin读取连续两个字段依赖空格或换行作为分隔符输入格式规范就没问题。stu[k-1]是差一索引的体现k从1开始下标从0开始。Python版本更简洁n, k map(int, input().split()) students [] for _ in range(n): sid, score input().split() students.append((sid, int(score))) students.sort(keylambda x: (-x[1], x[0])) sid, score students[k-1] print(sid, score)这里key用了元组(-x[1], x[0])负号表示降序学号升序作为次关键字。Python的sort是稳定排序但一旦key里加了次关键字稳定性就不重要了。注意score要转成int否则字符串比较会出现“9大于13”这种幻觉错误。4.2 手工推演一次查询过程我用一组小数据手工推演一遍确保边界和流程都对。假设学生成绩如下输入5 3 1001 90 1002 95 1003 85 1004 95 1005 90按“成绩降序、学号升序”排序后1002 951004 951001 901005 901003 85第3名对应下标2输出1001 90。这组数据特意设置了同分1001和1005都是90分但1001学号小排在前面。同时95分的两位同学占据了前两名所以第3名是90分的同学。如果题目要求的是“名次并列”第2名应该不存在或等于95分的同学那输出规则就完全不同了。这就是前面强调业务规则决定输出逻辑的原因。4.3 快速选择版本实现要点快速选择版本我只写partition和select两个函数。核心代码如下int partition(vectorStudent stu, int l, int r) { int idx l rand() % (r - l 1); swap(stu[idx], stu[r]); Student pivot stu[r]; int i l; for (int j l; j r; j) { if (cmp(stu[j], pivot)) { swap(stu[i], stu[j]); i; } } swap(stu[i], stu[r]); return i; } int selectKth(vectorStudent stu, int l, int r, int k) { while (l r) { int p partition(stu, l, r); if (p k) { return p; } else if (p k) { l p 1; } else { r p - 1; } } return -1; }调用时用int pos selectKth(stu, 0, n-1, k-1);然后输出stu[pos].id和stu[pos].score。注意这里k传入的是下标所以外部调用要减1。partition里比较用cmp(stu[j], pivot)因为cmp定义的顺序是从大到小所以最终结果是“第k大”放到了正确位置。随机基准用l rand() % (r - l 1)在r-l1是区间长度。快速选择的时间复杂度证明可以这样粗略理解理想情况下每次partition把区间对半分总工作量是n n/2 n/4 ... 2n所以是O(n)。如果基准选得不好每次都只缩小1个元素那总工作量是n (n-1) (n-2) ... O(n^2)。所以随机化非常重要。4.4 Python里面的heapq实现Python的heapq默认是最小堆。求第k大时维护一个大小为k的最小堆代码如下import heapq n, k map(int, input().split()) students [] heap [] for _ in range(n): sid, score input().split() score int(score) students.append((sid, score)) for sid, score in students: if len(heap) k: heapq.heappush(heap, (score, sid)) elif score heap[0][0]: heapq.heapreplace(heap, (score, sid)) score, sid heap[0] print(sid, score)堆里存的是元组(score, sid)最小堆会先按score比较再按sid比较。注意Python的heapreplace比先heappop再heappush更高效它是一次操作完成的。这里的heap[0]就是第k大的成绩而因为同分时会保留学号较小的在堆顶吗其实不一定如果成绩相同堆里最小的元组是学号小的那个这样会导致输出“第k大”时同分情况下输出学号小的。在有些题目规则下这可能是错的所以还是那句话先明确业务规则再选择算法。堆方案代码最简单但要注意它只能输出第k大的那个不能输出完整排名。如果你同时需要“前k名”和“第k名”堆可以做一点扩展把堆里的元素全部弹出并逆序排列就能得到从第k到第1的逆序榜单。5. 常见问题与排查技巧实录5.1 典型错误数组越界、索引差一数组越界和索引差一在这个题目里是双胞胎。最常见的错误是对k1的情况排序后直接输出stu[k]结果输出的是第2名因为把下标0和名次1搞混了。对kn的情况输出stu[k]直接越界访问因为vector只有n个元素最大下标是n-1。在快速选择的递归或循环中忘记把k减去1导致永远找不到目标位置最后返回-1或越界。排查这类问题的方法很朴素打印中间结果。我在调试时会在partition后打印p、l、r和当前p位置的成绩看着日志就能发现问题出在哪个区间判断。如果题目允许你提交还可以在本地准备几个极端用例k1、kn、n1、所有成绩相同。这四个用例一过索引类问题基本都能暴露。顺带说一个有意思的坑如果学生数量n用int读入但题目给的是10的9次方量级那int会溢出。虽然“n个学生”不太可能上亿但练习题为了卡算法确实会给出很大的n。我一般用long long读n和k存储下标时再用int因为vector下标本质上是个整数但n的范围决定了用int还是long long。这道题一般n不超过10的6次方int够用但养成long long的习惯没有坏处。5.2 并列名次时的业务逻辑坑并列名次的处理往往是这个题目里最考验“读题”能力的地方。我见过一份代码把排序结果直接当成名次输出结果题目要求“成绩相同名次相同”这代码就完全不对了。处理并列名次的代码模式一般是int rank 1; for (int i 0; i n; i) { if (i 0 stu[i].score stu[i-1].score) { rank i 1; } if (rank k) { cout stu[i].id stu[i].score endl; break; } }这个逻辑的关键是只有当前成绩小于上一个成绩时才更新名次为i1。如果成绩相同名次保持不变。这里我用的是“允许并列但占位”的规则也就是95分并列第1后下一个92分是第3名。如果你想要“并列后顺延”也就是第二名也行那需要把rank更新为上一个名次1而不是i1。两种规则差一行代码但输出结果完全不同。我强烈建议在题解笔记里把排名规则单独写一段因为这种业务语义非常容易在代码评审时被忽略。你在团队协作中也会遇到类似问题产品经理说“榜单要实现并列排名”但没有说清楚占不占位最后前端和后端各自理解上线后数据对不上。提前把规则定清楚用注释固定下来能省很多沟通成本。5.3 数据规模与内存如何估算遇到一个题先估算规模和内存是个好习惯。假设n100000每个Student包含一个string和一个int。string在64位系统上占用32字节本地小字符串优化下可能短字符串更省但学号稍微长一点就会分配堆内存int占4字节结构体对齐后可能占用40字节。十万个学生就是4MB左右内存完全不是问题。但如果n10的7次方一个结构体40字节就是400MB内存直接爆炸。内存不够怎么办降级方案是不要存完整结构体而是只存pairint, string或者两个平行数组。成绩用int学号用string分别存排序时对整个索引数组排序。这样能省掉结构体padding浪费的空间。当然这个程度的优化在这个题目里不需要但如果你以后处理海量数据这种“平行数组索引排序”的手法会经常用到。时间方面O(n log n)的sort在n10的6次方时大约需要几十毫秒到一百毫秒取决于平台环境。O(n)的快速选择在同样规模下可能是十几毫秒。如果平台时间限制是100ms排序可能擦边通过快速选择更稳妥。这也是我在做题时先看数据范围、再选算法的原因。5.4 一个容易被忽略的输入陷阱学号前导零学号前导零的问题我在前文提过一次这里再展开讲。假设学号是“00123”如果你用int读入它变成123输出就丢了两个零。这种错误在业务系统中尤其致命因为学号、工号这类标识符本质上就是字符串不是数字。用户看到“123”和“00123”是两条不同的记录你输出错了整个榜单就对不上。解决方法是把学号当字符串读入排序时按字符串规则即可。但字符串比较要注意如果学号长度不固定比如一个“5”一个“12”按字典序“12”会排在“5”前面但按学号数值语义排序应该“5”在前。所以更稳妥的做法是先按数值比较再按字符串比较。在C里可以写if (a.id.size() ! b.id.size()) return a.id.size() b.id.size(); return a.id b.id;如果题目没有特殊说明学号一般长度统一纯字典序就够了。但我见过太多长度不统一的测试数据所以这个判断逻辑加上有益无害。写代码时多做一步防御总比事后修bug强。5.5 调试技巧用随机数据对拍最后一个调试技巧也是我强烈推荐给所有刷题者的方法对拍。写一个暴力解法比如冒泡排序和一个优化解法比如快速选择用随机数据生成器生成大量测试用例然后对两个程序的结果进行比较。如果出现不一致就说明优化解法有bug。对拍脚本的伪代码很简单while true; do python3 gen.py input.txt ./brute input.txt ans1.txt ./optimized input.txt ans2.txt diff ans1.txt ans2.txt || break done这个技巧不仅适用于“谁考了第k名”适用于所有算法题。我有一次写快速选择分支条件写反了普通测试全过但用对拍跑了几千组随机数据后终于在一个极端数据上卡出了错误。没有对拍这种隐藏bug极难发现。刷题时习惯性写好对拍脚本等于给自己加了一道安全网。结尾我个人在实际操作中的体会是这道题最难的地方从来不是排序本身而是你能否在写代码前把“第k名”的语义、并列规则、输入格式边界全部想清楚。很多同学上来就写sort写完了才发现输出不对回头一行行读代码花了大量时间在调边界而不是在理解问题。我后来养成了一个习惯拿到任何题目先花三分钟手工模拟一遍小数据把输出结果写在纸上再动手写代码。这个习惯让我在这个题上几乎没有再犯过索引错误。另外如果你打算深入学习Top-K问题建议把排序、快速选择、堆三种方案全部实现一遍然后用对拍脚本互相验证这比你盯着题解看十遍都管用。