- 正确答案：成绩排名问题通常是指给定一组学生的成绩，要求按照成绩从高到低（或按特定规则）进行排序并输出对应的排名。若存在相同成绩，则根据并列处理规则决定排名方式（例如“并列同名次”或“并列后跳名次”）。常见实现方法是使用排序算法结合排名逻辑。示例输入：学生A: 85 学生B: 90 学生C: 85 学生D: 95 按成绩降序排列，并列同名次（中国式排名）：第1名：学生D（95）第2名：学生B（90）第3名：学生A、学生C（85）或者按“密集排名”（Dense Rank），即分数不同才改变排名。 - 解答思路： 1. 将每个学生的信息（姓名、成绩）封装成结构体或类。 2. 使用自定义排序函数，按成绩降序排序；若成绩相同，可按姓名字典序升序或其他规则稳定排序。 3. 遍历已排序的列表，根据前一个成绩是否等于当前成绩来判断是否分配新排名。 - 如果与前一个成绩相同且采用“并列不跳名次”，则排名不变； - 否则排名递增。 4. 输出每位学生的成绩和对应排名。关键点在于理解题目对“排名”的定义： - “标准排名”（Standard Rank）：相同成绩共享同一排名，后续名次跳过相应数量。如：95→第1名，90→第2名，85→第3名（两人），下一个为第5名。 - “密集排名”（Dense Rank）：相同成绩同名次，但下一名次只加1。如：95→1，90→2，85→3，即使有多个85也不影响下一等级为4。 - “行号排名”（Row Number）：每条记录独立编号，即使成绩相同也按顺序排开，相当于不分并列。校招中常考的是“并列同名次，后续顺延”（即标准排名）。 - 深度知识讲解： 1. **底层数据结构选择**： - 存储学生信息建议使用对象数组或结构体数组，便于字段访问。 - 可用 `vector>` 或自定义结构体 + 自定义比较器。 2. **排序算法原理**： - 实际开发中多使用库函数（如C++的sort()、Java的Arrays.sort），其底层通常是混合算法（Introsort：快速排序+堆排序+插入排序），时间复杂度O(n log n)。 - 排序必须是稳定的吗？如果要求成绩相同时按姓名排序，则需在比较函数中体现多级排序条件。 3. **排名生成逻辑**： - 初始化 rank = 1，prev_score = 第一个学生的成绩。 - 对于第 i 个学生（i ≥ 1）： if current_score == prev_score → 当前排名 = 上一个人的排名 else → 当前排名 = i + 1 （如果是行号法）或 rank++ 更通用做法是维护一个变量 last_rank 和 last_score。密集排名伪代码逻辑： dense_rank = 1 last_score = scores[0] result[0].rank = 1 for i from 1 to n-1: if scores[i] < last_score: dense_rank += 1 last_score = scores[i] result[i].rank = dense_rank 标准排名（竞争排名）： rank = 1 for i in range(n): if i == 0 or scores[i] < scores[i-1]: rank = i + 1 // 因为前面已有i个人，所以当前是第i+1名（允许并列跳名次） assign rank to student[i] 注意：“标准排名”中的 rank 并不是简单递增，而是位置+1，因为如果有重复，后面的名次要跳过重复人数。 4. **稳定性与比较器设计**：若需成绩相同时按姓名升序排列，比较函数应写为： if score_a != score_b: return score_a > score_b else: return name_a < name_b 这样可以保证结果的一致性和可预测性。 5. **时间和空间复杂度分析**： - 时间复杂度：O(n log n)，主要由排序决定。 - 空间复杂度：O(n)，用于存储学生数据和结果。 6. **扩展场景**： - 多科目总分排名？ - 加权平均分排名？ - 分班级/学院内排名？ - 实时排名系统（动态插入成绩后更新排名）→ 考察堆、平衡二叉树或数据库窗口函数。此时可能涉及： - 使用优先队列（最大堆）维护Top K； - 数据库中的 ROW_NUMBER(), RANK(), DENSE_RANK() 窗口函数； - Redis有序集合（ZSET）实现实时积分榜。 - 代码示例（C++风格伪代码）： ``` #include #include #include #include struct Student { std::string name; int score; int rank; }; bool compare(const Student& a, const Student& b) { if (a.score != b.score) { return a.score > b.score; // 成绩降序 } return a.name < b.name; // 成绩相同按名字升序 } void computeRank(std::vector& students) { if (students.empty()) return; std::sort(students.begin(), students.end(), compare); students[0].rank = 1; for (int i = 1; i < students.size(); ++i) { if (students[i].score == students[i-1].score) { students[i].rank = students[i-1].rank; // 并列同名次 } else { students[i].rank = i + 1; // 标准排名：跳名次 } } } // 输出示例 for (const auto& s : students) { std::cout << s.name << ": " << s.score << ", Rank " << s.rank << std::endl; } ``` - 扩展知识点补充： 1. 数据库中的排名函数（SQL）： - RANK(): 相同值同名次，之后跳号（如1,2,2,4） - DENSE_RANK(): 相同值同名次，之后不跳号（如1,2,2,3） - ROW_NUMBER(): 强制唯一编号（如1,2,3,4） SQL语句示例： SELECT name, score, RANK() OVER (ORDER BY score DESC) as ranking FROM students; 2. 分布式环境下的大规模排名： - 当数据量极大时，单机无法处理，需用MapReduce或Spark计算全局排名。 - 可先局部排序再归并，配合采样估算分位数。 3. 动态排名更新： - 使用平衡搜索树（如C++ set）或跳表维护有序序列； - 插入新成绩时，利用 lower_bound 找到插入位置，从而确定其排名。 4. 内存优化考虑： - 若只需返回Top K，可用最小堆维护K个最大元素，避免全排序，复杂度O(n log k)。综上所述，成绩排名问题虽表面简单，实则涵盖排序算法、比较器设计、排名策略选择、稳定性控制等多个计算机基础知识点，是校园招聘中考察编程思维与细节处理能力的经典题型。

伊戈尔电气面经

全站热榜

创作者周榜