“谁考了第k名”……这个题目当年我在刷题网站上第一次看到的时候心里冒出的想法是这也太基础了吧。可等到真的动手写才发现里面有结构体定义、自定义排序、并列名次处理、字符串学号这一类细节任何一个没想到都可能翻车。后来我带新人、给别人做代码评审也经常用这道题当入门试金石。你能不能在十分钟内写出一份不超时、不崩、边界全对的解法基本能看出你的工程基础扎不扎实。这篇文章就围绕“谁考了第k名”展开讲三件事题意到底在考什么、排序方案怎么选、实现和调试中有哪些坑。如果你刚学完排序想找题练手或者准备面试想快速回顾排序的知识点这份内容都适用。我尽量用大白话把每一步“为什么这么做”讲清楚而不是光丢一份参考答案。1. 题目解析先搞清楚它到底在考什么1.1 输入输出与数据组织典型的输入长这样4 2 1001 95 1002 92 1010 97 1020 90第一行两个整数n和k表示有 n 个学生问排名第 k 的学生是谁。接下来 n 行每行一个学号和一个成绩。按成绩从高到低排名输出排名第 k 的学生的学号和成绩格式一般是“学号 成绩”。上面这组数据里成绩从高到低排序是 101097、100195、100292、102090所以输出第 2 名是1001 95。这题看似直白但新手最容易掉坑的地方就是数据组织。我见过不少同学的初版代码是这样的用两个平行数组一个存score[0..n-1]一个存id[0..n-1]然后对score排序可id没有跟着动最后输出时学号和成绩就对不上号了。这是典型的“知道要排序、不知道排序要连带操作”的问题。正确做法是把学号和成绩绑成一个整体。在 C 里用struct在 Python 里用元组在 Java 里用对象或Map.Entry。一句话要排序的数据必须是一个整体而不是两个被强行分开的数组。1.2 排序规则降序还是升序并列怎么处理大多数版本默认为成绩降序也就是分数高的排前面。但这里有一个容易忽视的规则如果两个人的成绩一样怎么办有些题明确写“学号小的靠前”有些则根本没有提。实际做题时我建议一律按“成绩降序、学号升序”来处理。这样即使题目没有明确说明并列情况也不会因为顺序不稳定而输出错误结果。为什么会错这里牵涉到排序稳定性的概念C 的sort()是不稳定排序如果只按成绩排序相同成绩的学生顺序可能“乱跳”你用冒泡排序和用快排得到的结果可能不一样。Python 的sorted()是稳定排序会保留原始顺序。要让行为统一最好直接在自定义比较器里加上第二排序关键字。1.3 隐藏考点边界与复杂度这个题常被当成“入门送分题”但正因为太基础反而最能暴露基本功排名第 k 名k 从 1 开始数组下标却从 0 开始输出时要用k-1。n 可以到十万甚至百万O(n²) 的排序直接超时。学号不一定能转成整数可能是001这种串用整数读会把前导零丢掉输出就对不上。成绩有可能是浮点数浮点比较要考虑精度误差。这些细节没有处理好的话通过的样例再多也会在隐藏测试点上栽跟头。所以别看它简单每一行代码都值得认真对待。2. 排序方案选型从O(n²)到O(n log n)再到O(n)2.1 为什么别写冒泡排序冒泡排序、选择排序是教学用的现实中很少直接用来处理大数据量。冒泡排序的比较次数是n(n-1)/2n5000 的时候大约 1250 万次比较勉强能跑n100000 的时候就是大约 50 亿次比较按现代 CPU 每秒几亿次基本操作算也要好几秒甚至更久在刷题平台上妥妥超时。所以提交代码前先看看数据范围。n 超过 10000基本就该掏排序库了。不是说“不要自己写排序”而是“不要用低效的排序实现”。自己手写快速排序当然也可以但工程上用内建排序函数显然更稳因为标准库的排序是经过大量优化的。比如 C 的introsort在数据接近有序时会切换到插入排序避免快排退化到 O(n²)。2.2 工程首选标准库排序先列一下各语言常用的排序函数Cstd::sort或std::stable_sortPythonsorted()或list.sort()JavaCollections.sort()或Arrays.sort()稳定排序的意义我前面说过了如果只用成绩排序相同分的学生顺序不可控。用stable_sort或者自定义比较器里加入学号升序都能达到“成绩相同按学号排”的效果。复杂度方面标准库排序基本都是 O(n log n)对绝大多数题足够了。n100000 时O(n log n) 大概只要几十万次基本操作跟 O(n²) 完全不在一个量级上。2.3 进阶优化只要第k名真的需要全排序吗这里值得多想一步。如果只需要第 k 名是不是非得把全部 n 个人排好序答案是否定的。有一种叫nth_element的算法C STL 里有平均复杂度 O(n)。它只保证第 k 个位置上的元素是“如果全排序后位于第 k 个位置的那个元素”左侧都小于等于它右侧都大于等于它但左右内部不保证有序。也就是说它能直接告诉你谁是第 k 名但不告诉你第 1 到第 k-1 名分别是多少。还有基于堆的 TopK 思路维护一个大小为 k 的小顶堆遍历成绩时如果新元素比堆顶大就替换堆顶最后堆顶就是第 k 名。这个思路在“只关心前 k 名”时很有用尤其是在海量数据场景下内存装不下全部数据时只能用这种滑动方式处理。不过对于“谁考了第 k 名”这道题n 通常不会大到内存装不下所以 O(n log n) 的全排序已经足够。但面试时如果能把nth_element或堆方法讲清楚会是很不错的加分项。2.4 自定义比较器的正确写法C 自定义排序规则时要注意返回值语义返回true表示第一个参数排在第二个参数前面。按“分数降序、学号升序”的逻辑比较器可以写成bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; }Python 的写法更简洁用key参数配合元组students.sort(keylambda x: (-x[1], x[0]))这里用负号实现降序第二个元素是学号默认升序。但前提是分数可以取负如果成绩是字符串或者包含其他不可取负的类型就得用functools.cmp_to_key转成比较器。这个函数是 Python 里比较冷门但很实用的知识点遇到复杂排序规则时能救急。3. 多语言实现与关键代码解读3.1 C 完整示例C 实现的完整代码如下我加了注释重点说明每一段在干什么#include cstdio #include cstring #include algorithm struct Student { char id[20]; // 学号用字符串存防止前导零丢失 double score; // 成绩用 double }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; // 分数降序 return strcmp(a.id, b.id) 0; // 学号升序 } int main() { int n, k; scanf(%d %d, n, k); Student stu[100005]; for (int i 0; i n; i) { scanf(%s %lf, stu[i].id, stu[i].score); } std::sort(stu, stu n, cmp); printf(%s %.0f\n, stu[k - 1].id, stu[k - 1].score); return 0; }几个细节说一下。第一为什么用scanf/printf而不是cin/cout因为当 n 很大时cin/cout的默认同步会导致输入输出性能明显变差容易超时。用scanf/printf最稳妥。如果你更喜欢cin/cout记住在程序开头加上std::ios::sync_with_stdio(false); std::cin.tie(nullptr);把同步关掉。第二为什么学号用字符串因为很多题目里的学号是固定长度的数字串比如000123用int读进去就变成了123输出时对不上原数据。用字符串存储是最保险的比较时用strcmp实现字典序升序。第三为什么成绩用double因为成绩可能是95.5这种浮点数。输出时%.0f表示保留零位小数如果你确定的输出格式要求带小数自己调整格式化字符串即可。3.2 Python 完整示例Python 实现更短但同样有需要注意的地方import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) k int(data[1]) students [] idx 2 for _ in range(n): sid data[idx] score float(data[idx 1]) students.append((sid, score)) idx 2 students.sort(keylambda x: (-x[1], x[0])) print(students[k - 1][0], int(students[k - 1][1])) if __name__ __main__: main()先说排序那行students.sort(keylambda x: (-x[1], x[0]))。Python 的sort是稳定排序key返回一个元组第一关键字是成绩的相反数实现降序第二关键字是学号字符串实现升序。这个写法很简洁但要注意如果成绩不是数值型负号会报错这时改用cmp_to_keyfrom functools import cmp_to_key def cmp(a, b): if a[1] ! b[1]: return -1 if a[1] b[1] else 1 return -1 if a[0] b[0] else 1 students.sort(keycmp_to_key(cmp))再说输入解析用sys.stdin.read()一次性读完避免多次input()的 IO 开销。这在 n 很大时能明显提速。float转换成绩是为了支持浮点数如果确定成绩是整数改成int也行。3.3 Java 与常见变体提醒Java 里最直接的写法是用ListStudent加自定义ComparatorCollections.sort(students, new ComparatorStudent() { Override public int compare(Student a, Student b) { if (a.score ! b.score) { return Double.compare(b.score, a.score); // 降序 } return a.id.compareTo(b.id); // 学号升序 } });Java 8 之后可以用 Lambda 简化students.sort(Comparator.comparing(Student::getScore).reversed() .thenComparing(Student::getId));这里要留意Comparator.comparing(...).reversed()的坑reversed()会把整个比较器反转包括后面thenComparing的部分。如果你想要“成绩降序、学号升序”建议把reversed()放在第一个字段上而不是整个链上。我见过同事在这里写出“成绩降序、学号也降序”的诡异结果排查了半天。4. 高频踩坑与问题排查实录4.1 数组下标越界排名第 k 对应的是排序后数组的下标k-1。这个错误太常见了尤其是新手。有人直接写stu[k]当 k 等于 n 的时候就越界访问了。排查技巧很简单构造n1, k1的边界用例一跑就现原形。4.2 学号前导零丢失用int存学号会丢掉前导零。比如学号是001读成1排序和输出都错。如果题目说学号是纯数字但位数固定必须用字符串处理。有同学会问“那排序的时候学号不就是要按数字大小吗”其实大部分题目里学号只是标识符并列成绩时按学号升序多半是字典序或原始输入顺序用字符串完全没问题。如果真的要求按数字大小可以字符串转整数后比较但输出时还是要保留原始字符串。4.3 浮点数比较误差成绩是浮点数时直接用比较可能出问题。比如95.5和95.5在浮点表示上可能不完全一样排序时如果分数被认为不相等会排错顺序。建议要么用整数存储比如把成绩乘以 10 或 100 变成整数要么在比较时用误差范围比如fabs(a.score - b.score) 1e-9就认为相等。这类精度问题在“判断是否并列”的场景里特别容易踩。4.4 输入输出的性能坑当 n 很大时C 的cin/cout默认同步会导致超时。我见过一个很典型的案例代码逻辑完全正确但就是超时加上ios::sync_with_stdio(false)之后立刻通过了。Python 则要少用input()改用sys.stdin.read()或sys.stdin.buffer.read()后者还能再快一点。这不是玄学是 IO 缓冲机制的问题。4.5 并列名次输出“1 2 2 4”这种怎么处理很多题不会直接告诉你“第 k 名”是指“排名位置”还是“并列名次”。如果要求输出真正竞赛里的名次——即分数相同的人名次相同后续名次跳过——那就不能只靠排序后取k-1了。做法是排序后遍历一遍手动计算名次rank 1 for i in range(n): if i 0 and students[i][1] ! students[i - 1][1]: rank i 1 if rank k: print(students[i][0], students[i][1]) break注意rank的更新逻辑是“和前一个人分数不同名次才变成当前下标加一”。相同分数的人共享同一个名次。这个坑一定要记下来因为很多人想当然地认为名次就是下标加一遇到并列就全错了。5. 从“第k名”到实际业务场景5.1 奖学金评定与榜单制作现实中的奖学金评定通常要按“成绩、德育、竞赛加分”等多关键字排序。本质上就是这道题的扩展把单一成绩换成综合得分把学号换成姓名排序规则变成多字段组合。比如“综合分降序、综合分相同按德育分降序、再相同按学号升序”这一串规则用 C 自定义比较器或 Python 的sort(key...)都很容易实现。这类需求在写高校、培训机构的管理系统时非常常见。与其每次都临时写排序逻辑不如把“比较器”设计成一个可配置的规则链。这也是为什么我强调“自定义比较器”这件事值得认真掌握它不只是刷题用的。5.2 TopN榜单与流式数据游戏排行榜、电商热销榜本质上都是 TopN 问题数据量巨大内存装不下全部数据或者数据实时到达不能每次全量排序。这时候要用堆维护一个大小为 N 的小顶堆新数据比堆顶好就替换最后堆里的就是 TopN。这也是“谁考了第 k 名”在工程中真正的形态。我举一个实际例子给一个日活百万的 App 做“今日热帖 Top 100”如果每次刷新都把所有帖子排序一遍压力非常大。更好的做法是维护一个长度为 100 的小顶堆新帖子的热度值进堆最终只看堆里的 100 条。复杂度从 O(n log n) 降到了 O(n log k)k100 时差距非常明显。5.3 面试考点串联这道题可以引出一串面试高频考点排序稳定性、自定义比较器、复杂度量级感、边界输入处理、TopK 的堆与快速选择。面试官问“排序算法了解哪些”之后经常接着问“如果只要求第 k 大元素你怎么做”。如果你只答“排个序取第 k 个”不会扣分但如果你能主动说出nth_element的思路、堆方法的适用场景效果会好很多。我个人比较推荐的练习路径是先用最朴素的方式把题写对然后用标准库排序改写最后再想一步“如果 n 是一亿怎么办”。这三步走完这道题才算真正吃透。最后分享一点个人体会。我的确用这道题压过不少新人的入职考核题。写出来很容易但能不能考虑到并列名次、数据范围、字符串学号、IO 性能才是拉开差距的地方。不要觉得“送分题”就不用认真对待越是基础的题越能看出一个人有没有工程习惯。如果你愿意把它当成一道扩展题集来做哪怕只花半小时收获也会比刷十道重复的题大。