企业官网建设流程全解析

“谁考了第k名”……这个题目当年我在刷题网站上第一次看到的时候，心里冒出的想法是：这也太基础了吧。可等到真的动手写，才发现里面有结构体定义、自定义排序、并列名次处理、字符串学号这一类细节，任何一个没想到都可能翻车。后来我带新人、给别人做代码评审，也经常用这道题当入门试金石。你能不能在十分钟内写出一份不超时、不崩、边界全对的解法，基本能看出你的工程基础扎不扎实。

这篇文章就围绕“谁考了第k名”展开，讲三件事：题意到底在考什么、排序方案怎么选、实现和调试中有哪些坑。如果你刚学完排序想找题练手，或者准备面试想快速回顾排序的知识点，这份内容都适用。我尽量用大白话，把每一步“为什么这么做”讲清楚，而不是光丢一份参考答案。

1. 题目解析：先搞清楚它到底在考什么

1.1 输入输出与数据组织

典型的输入长这样：

4 2 1001 95 1002 92 1010 97 1020 90

第一行两个整数n和k，表示有 n 个学生，问排名第 k 的学生是谁。接下来 n 行，每行一个学号和一个成绩。按成绩从高到低排名，输出排名第 k 的学生的学号和成绩，格式一般是“学号 成绩”。上面这组数据里，成绩从高到低排序是 1010（97）、1001（95）、1002（92）、1020（90），所以输出第 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)/2，n=5000 的时候大约 1250 万次比较，勉强能跑；n=100000 的时候就是大约 50 亿次比较，按现代 CPU 每秒几亿次基本操作算，也要好几秒甚至更久，在刷题平台上妥妥超时。

所以提交代码前先看看数据范围。n 超过 10000，基本就该掏排序库了。不是说“不要自己写排序”，而是“不要用低效的排序实现”。自己手写快速排序当然也可以，但工程上用内建排序函数显然更稳，因为标准库的排序是经过大量优化的。比如 C++ 的introsort，在数据接近有序时会切换到插入排序，避免快排退化到 O(n²)。

2.2 工程首选：标准库排序

先列一下各语言常用的排序函数：

• C++：std::sort或std::stable_sort
• Python：sorted()或list.sort()
• Java：Collections.sort()或Arrays.sort()

稳定排序的意义我前面说过了，如果只用成绩排序，相同分的学生顺序不可控。用stable_sort，或者自定义比较器里加入学号升序，都能达到“成绩相同按学号排”的效果。

复杂度方面，标准库排序基本都是 O(n log n)，对绝大多数题足够了。n=100000 时，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(key=lambda 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(key=lambda x: (-x[1], x[0])) print(students[k - 1][0], int(students[k - 1][1])) if __name__ == "__main__": main()

先说排序那行：students.sort(key=lambda x: (-x[1], x[0]))。Python 的sort是稳定排序，key返回一个元组，第一关键字是成绩的相反数，实现降序；第二关键字是学号字符串，实现升序。这个写法很简洁，但要注意如果成绩不是数值型，负号会报错，这时改用cmp_to_key：

from 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(key=cmp_to_key(cmp))

再说输入解析：用sys.stdin.read()一次性读完，避免多次input()的 IO 开销。这在 n 很大时能明显提速。float转换成绩是为了支持浮点数，如果确定成绩是整数，改成int也行。

3.3 Java 与常见变体提醒

Java 里最直接的写法是用List<Student>加自定义Comparator：

Collections.sort(students, new Comparator<Student>() { @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 的时候就越界访问了。排查技巧很简单：构造n=1, k=1的边界用例，一跑就现原形。

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)，k=100 时差距非常明显。

5.3 面试考点串联

这道题可以引出一串面试高频考点：排序稳定性、自定义比较器、复杂度量级感、边界输入处理、TopK 的堆与快速选择。面试官问“排序算法了解哪些”之后，经常接着问“如果只要求第 k 大元素，你怎么做”。如果你只答“排个序取第 k 个”，不会扣分，但如果你能主动说出nth_element的思路、堆方法的适用场景，效果会好很多。

我个人比较推荐的练习路径是：先用最朴素的方式把题写对，然后用标准库排序改写，最后再想一步“如果 n 是一亿怎么办”。这三步走完，这道题才算真正吃透。

最后分享一点个人体会。我的确用这道题压过不少新人的入职考核题。写出来很容易，但能不能考虑到并列名次、数据范围、字符串学号、IO 性能，才是拉开差距的地方。不要觉得“送分题”就不用认真对待，越是基础的题，越能看出一个人有没有工程习惯。如果你愿意把它当成一道扩展题集来做，哪怕只花半小时，收获也会比刷十道重复的题大。