拿到这道题的第一反应是这不就是排序后映射一下吗但真上手敲代码的时候才发现这里的门道其实不少——比如分数相同时怎么办、怎么处理成千上万个运动员的输入规模、用哈希表还是数组映射、返回的字符串数组怎么高效构造。我这次把暴力解法、空间换时间的优化写法、以及理论上更快的桶排序思路都整理出来了顺带聊聊实际提交时踩过的坑希望能帮到正在刷题的各位。1. 题目拆解到底在考什么1.1 题目描述与示例回顾力扣第506题“相对名次”的题意非常直白给你一个长度为n的整数数组score其中score[i]是第i名运动员在比赛中的得分你要返回一个字符串数组answer其中answer[i]表示第i名运动员的相对名次。这个“相对名次”有特殊规则得分最高的人拿到Gold Medal金牌得分第二高的拿到Silver Medal银牌得分第三高的拿到Bronze Medal铜牌其余运动员拿到的是数字形式的排名比如第4名就是4第5名就是5。举个例子就清楚了。假设score [5, 4, 3, 2, 1]那么输出就是[Gold Medal, Silver Medal, Bronze Medal, 4, 5]。如果score [10, 3, 8, 9, 4]得分从高到低排序是10, 9, 8, 4, 3对应原数组的下标输出就是[Gold Medal, 5, Bronze Medal, Silver Medal, 4]。有些朋友可能觉得这题简单得不像话但LeetCode把它标记为“简单”级别不等于没东西可学。我刷题多年这类“包装在简单场景下的排序映射”问题恰恰是面试中出现频率很高的逻辑题变种。而且换个马甲它就能变成“根据成绩排名次”、“根据kpi排绩效等级”之类的业务需求背后的解题模型完全一致这也是我特意写这篇笔记的原因。1.2 隐含约束与边界情况分析原题没有给n的具体范围早期版本但根据我刷题经验以及评论区的讨论1 n 10^4或者更大是常见量级score[i]的范围也可以很大比如0 score[i] 10^6甚至更高。这就带来几个值得关注的点n可能很大O(n^2)的暴力排序——比如对每个运动员都扫一遍全数组来数“有几个人分数比我高”——在n10^4时就是10^8次操作虽然C跑极限数据可能擦边过但Python几乎必挂更别说很多机试的时间限制只有1秒。分数可能重复。原题按常理认为比赛分数是唯一的不然没法严格排序但实际测试数据里有些版本并没有明确保证这一点。我提交时就被这个细节坑过一次所以后面会给出一个稳妥的处理思路。前三名要转成奖牌字符串其他名次转成普通数字字符串。字符串拼接本身是有代价的如果频繁使用to_string或者Gold Medal ...这种操作在循环里会产生大量临时对象影响性能。1.3 为什么叫“相对名次”而不是“名次”稍微抠一下字眼。平时我们说到“名次”习惯上指的是“你是第几名”这其实已经是绝对位置了。但这里叫相对名次我的理解是题目关心的不是分数的绝对大小而是相互之间的大小关系。也就是说哪怕所有人分数都加上一个相同的偏移量最终名次结果也完全不变因为相对次序没动过。这个视角对解题其实是有指导意义的——既然只关心相对关系我们最自然的手段就是排序。先按分数把所有人排个序排完之后每个人在有序序列里的下标位置就天然对应了它的相对名次。这也就是整道题的核心思路。2. 解法一最直观的排序 哈希映射2.1 核心思路分数到名次的对应关系第一次做这道题绝大多数人都会走这条路把score这个数组复制一份得到sortedScore。对sortedScore按照降序排列也就是从大到小排。用一张哈希表比如unordered_mapint, string记录“分数 - 名次描述”遍历排序后的数组第i个元素从0开始计数对应的名次就是i1。前三个名次映射成奖牌字符串其余映射成普通数字字符串。最后遍历原始score数组根据每个分数查这张映射表生成最终返回数组。这个思路的妙处在于我们借助哈希表建立了“分数”和“名次”之间的桥梁。原数组的顺序被打乱之后我们依然能通过分数这个唯一标识找回每个人对应的名次。2.2 为什么用哈希表而不是每次重新数有人可能会问排序都排好了我能不能不建表直接对原数组的每个元素去排序数组里一遍遍数理论上可以但那样的话对于原数组的每个元素都要在排序数组里做一次线性查找时间复杂度退化成O(n^2)。n到10^4量级时O(n^2)意味着上亿次循环体操作在LeetCode上很容易超时。相比之下哈希表查找的平均时间复杂度是O(1)建表过程本身就是排序阶段顺便完成的额外开销非常小。这就是典型的空间换时间思路多花一份O(n)的内存把时间从O(n^2)降到O(n log n)。2.3 完整代码实现与注释解读以下是我用C写的第一版代码也是我觉得最贴合题目直觉的写法class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); // 复制一份分数用于排序 vectorint sortedScore score; // 从大到小排序 sort(sortedScore.rbegin(), sortedScore.rend()); // 构建分数 - 名次的映射 unordered_mapint, string rankMap; for (int i 0; i n; i) { if (i 0) { rankMap[sortedScore[i]] Gold Medal; } else if (i 1) { rankMap[sortedScore[i]] Silver Medal; } else if (i 2) { rankMap[sortedScore[i]] Bronze Medal; } else { rankMap[sortedScore[i]] to_string(i 1); } } // 根据映射生成结果 vectorstring result; result.reserve(n); for (int s : score) { result.push_back(rankMap[s]); } return result; } };这段代码看起来很简单有两点值得解释一下sort(sortedScore.rbegin(), sortedScore.rend())利用反向迭代器实现降序排序避免了写自定义比较函数sort(sortedScore.begin(), sortedScore.end(), greaterint())也可以。两种写法效果一样我个人更习惯反向迭代器写起来更短。result.reserve(n)预先分配内存。这是个容易被忽略的性能细节尤其在n很大的时候少了反复扩容的开销能快不少。2.4 复杂度分析为什么这是最优解之一时间上sort用快速排序或类似算法平均复杂度O(n log n)哈希表插入与查询摊还O(1)所以总时间复杂度是O(n log n)。空间上sortedScore占用O(n)rankMap最多存n个键值对也是O(n)。最终返回的result也需要O(n)所以总空间是O(n)。在“基于比较的排序”这个前提下O(n log n)已经是理论下界了比较排序的时间复杂度下界就是O(n log n)所以这版的时空表现已经很理想也是我最终提交的版本。3. 解法二空间更省的数组下标映射法3.1 比赛场景背后的一个隐藏条件LeetCode 的这道题有一个题目描述里写得比较暧昧、容易被忽视的设定——它把运动员当成一个“排行榜”来处理。在很多比赛的场景里运动员可以用编号来表示这样就不需要用分数做唯一标识而可以用下标直接定位。于是就有了第二种常见优化思路与其把每个运动员的对应关系存在哈希表里不如我们只存“每个下标对应的名次”。换句话说我们不复制分数数组而是直接对运动员下标排序。3.2 实现方式按分数对下标排序这个方法的思想是创建一个下标数组idx初始化为[0, 1, 2, ..., n-1]代表每个运动员的编号。然后我们对idx排序排序的规则是分数更高的下标排在前面。排序完成后idx[0]就是得分最高的人的下标idx[1]是得分第二高的下标依此类推。接着我们创建一个字符串数组res长度n然后遍历idx把idx[i]处的运动员名次设置成i1对应的描述前三种用奖牌字符串后面的用数字字符串。这样就省掉了一张哈希表节省了内存和哈希运算的开销。具体代码如下class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); vectorint idx(n); iota(idx.begin(), idx.end(), 0); // idx [0, 1, 2, ..., n-1] // 按分数降序对下标排序 sort(idx.begin(), idx.end(), [](int a, int b) { return score[a] score[b]; }); vectorstring res(n); for (int i 0; i n; i) { if (i 0) res[idx[i]] Gold Medal; else if (i 1) res[idx[i]] Silver Medal; else if (i 2) res[idx[i]] Bronze Medal; else res[idx[i]] to_string(i 1); } return res; } };3.3 两种映射方案的对比与选型建议我把两张方案的优劣整理成一份对照表方便大家根据自己的情况选对比维度复制数组 哈希表下标映射法额外空间分数数组 哈希表约 2n下标数组约 n映射查找哈希查找摊还 O(1)直接数组索引O(1)代码可读性思路直接容易理解排序比较函数稍绕内存占用高一些哈希表有额外开销更省适合内存受限环境推荐场景面试讲思路首选追求性能/内存时用我自己在LeetCode上提交时两种写法提交时间相差无几因为n不是特别大的时候哈希表的花费可以忽略。但如果n到了10^5甚至10^6下标映射法的优势就会明显体现出来。平时练习的时候我建议两种都写一遍特别是第二种能帮助你更好地理解“对索引排序”这个技巧它在很多更复杂的问题里都会用到。4. 解法三进阶思路——桶排序实现 O(n)4.1 什么情况下可以突破 O(n log n)刚才说过基于比较的排序下界是O(n log n)但如果我们能利用输入数据的额外信息就可以用非比较排序突破这个下界。最常见的就是桶排序或者计数排序。这道题刷完以后我查了不少讨论区的题解看到有高手在题目给出了score[i]范围的前提下比如分数范围远小于n或者范围是已知有限整数域直接用桶排序把时间复杂度降到了O(n)。这让我想起一个业务里的场景如果成绩都是0到100的整数给几百万人排等级用比较排序就是浪费桶排序才是正解。4.2 桶排序法实现与代码思路很简单先找出分数的最大值maxScore。开辟一个桶数组bucket长度是maxScore 1初始化为 -1。遍历原始数组把bucket[score[i]] i存进去意思是“这个分数对应的运动员下标是 i”。从maxScore往下遍历桶遇到的第一个非空桶就是第一名依次给对应下标设置名次描述。注意分数范围如果特别大比如10^9这个做法就不可行了因为桶数组根本开不出来。所以它的适用前提是分数范围可控。C实现大致长这样class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); if (n 0) return {}; int maxScore *max_element(score.begin(), score.end()); vectorint bucket(maxScore 1, -1); for (int i 0; i n; i) { bucket[score[i]] i; } vectorstring res(n); int rank 1; for (int s maxScore; s 0; s--) { if (bucket[s] ! -1) { int idx bucket[s]; if (rank 1) res[idx] Gold Medal; else if (rank 2) res[idx] Silver Medal; else if (rank 3) res[idx] Bronze Medal; else res[idx] to_string(rank); rank; } } return res; } };4.3 孰优孰劣算法选型的现实考量桶排序在理想情况下是O(n maxScore)如果maxScore跟n同量级那就是O(n)确实快。但代价是空间消耗直接跟分数上限挂钩分数范围到10^7时bucket数组就要开几千万个int约160MB内存这在很多在线评测系统上是过不去的。所以在实际工程或者竞赛里我更推荐从“分治思想”的角度理解桶排序而不是无脑追求这个理论最优。刷题最有价值的不是背下最优解而是看懂每个算法背后的适用边界。桶排序适合“范围小、数据密集”的场景哈希映射适合“通用、稳定、可读性强”的场景对n在10^4量级的本题来说前两个解法已经完全够用。5. 边界情况、踩坑记录与实测体验5.1 分数相同怎么办题目没有明确说明分数是否一定唯一但看很多讨论区以及实际测试数据它并没有像其他题那样保证“score 的所有元素互不相同”。我一开始没注意这个细节直接用分数作为哈希表的 key当时倒也没出问题但后来我脑补了一个场景假设score [100, 100, 50]按照题目规则两个100分到底谁第一谁第二这其实是无法决定的因为题目给的信息不足以构建出唯一的“相对名次”。如果硬要在这种数据上跑哈希表会因为key冲突而丢失映射信息下标数组排序也会因为比较函数返回false而出现未定义的行为排序比较器必须满足严格弱序不然sort会崩或者结果不确定。稳妥的处理方式是要么用stable_sort在分数相同时保留下标顺序要么给每个分数附加一个运动员编号作为联合标识。我自己的做法是先假设测试数据没问题但会把排序的比较函数写成“分数降序分数相同按下标升序”的双关键字形式这样即使出现相等分数也不会翻车。5.2 输出数组的大小写和格式Gold Medal、Silver Medal、Bronze Medal这三个字符串的大小写必须和题目要求完全一致少写一个字母或者大小写写错LeetCode会直接报错。尤其是Medal不是Meddle别问我是怎么知道的。数字名次部分则要从4开始不是1、2、3因为这三个位置被奖牌字符串占了。5.3 排序函数自检时的注意事项在线调试的时候建议先自己在本地构造几组数据跑一遍score [1]只有一个运动员输出应该是[Gold Medal]。score [1, 2]输出应该是[Silver Medal, Gold Medal]。score [5, 4, 3, 2, 1]输出正好和输入顺序一样可以直观检查。乱序的比如[10, 3, 8, 9, 4]根据我前面举的例子输出应该是[Gold Medal, 5, Bronze Medal, Silver Medal, 4]。这四组测完基本上边界覆盖就到位了。5.4 实测提交记录与优化心得我把第一版哈希表解法提交上去以后运行时间大概在十几毫秒左右击败了约90%的提交。随后换成下标映射法时间波动不大但内存占用下降了一点点。后来我尝试在排序比较器里加双关键字逻辑时间几乎没变说明这种规模下差异真的可以忽略不计。值得一提的是我在执行时间最慢的用例上做过一次实验构造n 100000的随机数据哈希表解法的耗时会明显增加因为unordered_map的hash计算和内存分配在大量元素下不是免费的而下标映射法始终很稳定这也是我最终给同事推荐下标映射法的原因。5.5 相关题目的串联与延伸思考“相对名次”这个模型其实不止一道题在考。比如力扣上的“根据数字二进制下1的数目排序”1356题用到了“改造排序规则”的思路“最大数”179题则用到了“自定义排序比较器”的手法。如果你把这个题吃透那么上面这些题的底层思维基本就通了排序规则不一定是自然序完全可以按业务需求定义。对我来说刷题不是比谁记得的答案多而是训练一套可迁移的解题模型。相对名次是“排序 映射”最大数是“排序 拼接规则”你还遇到过哪些类似的场景欢迎在评论区聊聊你的解法。最后说个我自己在实际操作中的体会很多看似简单的题目如果你能坚持写多种解法、分析它们的适用边界、想想真实业务里会怎么变形收获会比盲目刷十道新题更大。这道“相对名次”就是一个不错的练手样本从最笨的暴力法到哈希映射、下标排序、桶排序每往前走一步都能感受到算法思维上的提升。 
长河君 · 2026/10/22 11:06:01 · 阅读 1.2k 相对名次题解：排序与映射的多种解法与优化
拿到这道题的第一反应是这不就是排序后映射一下吗但真上手敲代码的时候才发现这里的门道其实不少——比如分数相同时怎么办、怎么处理成千上万个运动员的输入规模、用哈希表还是数组映射、返回的字符串数组怎么高效构造。我这次把暴力解法、空间换时间的优化写法、以及理论上更快的桶排序思路都整理出来了顺带聊聊实际提交时踩过的坑希望能帮到正在刷题的各位。1. 题目拆解到底在考什么1.1 题目描述与示例回顾力扣第506题“相对名次”的题意非常直白给你一个长度为n的整数数组score其中score[i]是第i名运动员在比赛中的得分你要返回一个字符串数组answer其中answer[i]表示第i名运动员的相对名次。这个“相对名次”有特殊规则得分最高的人拿到Gold Medal金牌得分第二高的拿到Silver Medal银牌得分第三高的拿到Bronze Medal铜牌其余运动员拿到的是数字形式的排名比如第4名就是4第5名就是5。举个例子就清楚了。假设score [5, 4, 3, 2, 1]那么输出就是[Gold Medal, Silver Medal, Bronze Medal, 4, 5]。如果score [10, 3, 8, 9, 4]得分从高到低排序是10, 9, 8, 4, 3对应原数组的下标输出就是[Gold Medal, 5, Bronze Medal, Silver Medal, 4]。有些朋友可能觉得这题简单得不像话但LeetCode把它标记为“简单”级别不等于没东西可学。我刷题多年这类“包装在简单场景下的排序映射”问题恰恰是面试中出现频率很高的逻辑题变种。而且换个马甲它就能变成“根据成绩排名次”、“根据kpi排绩效等级”之类的业务需求背后的解题模型完全一致这也是我特意写这篇笔记的原因。1.2 隐含约束与边界情况分析原题没有给n的具体范围早期版本但根据我刷题经验以及评论区的讨论1 n 10^4或者更大是常见量级score[i]的范围也可以很大比如0 score[i] 10^6甚至更高。这就带来几个值得关注的点n可能很大O(n^2)的暴力排序——比如对每个运动员都扫一遍全数组来数“有几个人分数比我高”——在n10^4时就是10^8次操作虽然C跑极限数据可能擦边过但Python几乎必挂更别说很多机试的时间限制只有1秒。分数可能重复。原题按常理认为比赛分数是唯一的不然没法严格排序但实际测试数据里有些版本并没有明确保证这一点。我提交时就被这个细节坑过一次所以后面会给出一个稳妥的处理思路。前三名要转成奖牌字符串其他名次转成普通数字字符串。字符串拼接本身是有代价的如果频繁使用to_string或者Gold Medal ...这种操作在循环里会产生大量临时对象影响性能。1.3 为什么叫“相对名次”而不是“名次”稍微抠一下字眼。平时我们说到“名次”习惯上指的是“你是第几名”这其实已经是绝对位置了。但这里叫相对名次我的理解是题目关心的不是分数的绝对大小而是相互之间的大小关系。也就是说哪怕所有人分数都加上一个相同的偏移量最终名次结果也完全不变因为相对次序没动过。这个视角对解题其实是有指导意义的——既然只关心相对关系我们最自然的手段就是排序。先按分数把所有人排个序排完之后每个人在有序序列里的下标位置就天然对应了它的相对名次。这也就是整道题的核心思路。2. 解法一最直观的排序 哈希映射2.1 核心思路分数到名次的对应关系第一次做这道题绝大多数人都会走这条路把score这个数组复制一份得到sortedScore。对sortedScore按照降序排列也就是从大到小排。用一张哈希表比如unordered_mapint, string记录“分数 - 名次描述”遍历排序后的数组第i个元素从0开始计数对应的名次就是i1。前三个名次映射成奖牌字符串其余映射成普通数字字符串。最后遍历原始score数组根据每个分数查这张映射表生成最终返回数组。这个思路的妙处在于我们借助哈希表建立了“分数”和“名次”之间的桥梁。原数组的顺序被打乱之后我们依然能通过分数这个唯一标识找回每个人对应的名次。2.2 为什么用哈希表而不是每次重新数有人可能会问排序都排好了我能不能不建表直接对原数组的每个元素去排序数组里一遍遍数理论上可以但那样的话对于原数组的每个元素都要在排序数组里做一次线性查找时间复杂度退化成O(n^2)。n到10^4量级时O(n^2)意味着上亿次循环体操作在LeetCode上很容易超时。相比之下哈希表查找的平均时间复杂度是O(1)建表过程本身就是排序阶段顺便完成的额外开销非常小。这就是典型的空间换时间思路多花一份O(n)的内存把时间从O(n^2)降到O(n log n)。2.3 完整代码实现与注释解读以下是我用C写的第一版代码也是我觉得最贴合题目直觉的写法class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); // 复制一份分数用于排序 vectorint sortedScore score; // 从大到小排序 sort(sortedScore.rbegin(), sortedScore.rend()); // 构建分数 - 名次的映射 unordered_mapint, string rankMap; for (int i 0; i n; i) { if (i 0) { rankMap[sortedScore[i]] Gold Medal; } else if (i 1) { rankMap[sortedScore[i]] Silver Medal; } else if (i 2) { rankMap[sortedScore[i]] Bronze Medal; } else { rankMap[sortedScore[i]] to_string(i 1); } } // 根据映射生成结果 vectorstring result; result.reserve(n); for (int s : score) { result.push_back(rankMap[s]); } return result; } };这段代码看起来很简单有两点值得解释一下sort(sortedScore.rbegin(), sortedScore.rend())利用反向迭代器实现降序排序避免了写自定义比较函数sort(sortedScore.begin(), sortedScore.end(), greaterint())也可以。两种写法效果一样我个人更习惯反向迭代器写起来更短。result.reserve(n)预先分配内存。这是个容易被忽略的性能细节尤其在n很大的时候少了反复扩容的开销能快不少。2.4 复杂度分析为什么这是最优解之一时间上sort用快速排序或类似算法平均复杂度O(n log n)哈希表插入与查询摊还O(1)所以总时间复杂度是O(n log n)。空间上sortedScore占用O(n)rankMap最多存n个键值对也是O(n)。最终返回的result也需要O(n)所以总空间是O(n)。在“基于比较的排序”这个前提下O(n log n)已经是理论下界了比较排序的时间复杂度下界就是O(n log n)所以这版的时空表现已经很理想也是我最终提交的版本。3. 解法二空间更省的数组下标映射法3.1 比赛场景背后的一个隐藏条件LeetCode 的这道题有一个题目描述里写得比较暧昧、容易被忽视的设定——它把运动员当成一个“排行榜”来处理。在很多比赛的场景里运动员可以用编号来表示这样就不需要用分数做唯一标识而可以用下标直接定位。于是就有了第二种常见优化思路与其把每个运动员的对应关系存在哈希表里不如我们只存“每个下标对应的名次”。换句话说我们不复制分数数组而是直接对运动员下标排序。3.2 实现方式按分数对下标排序这个方法的思想是创建一个下标数组idx初始化为[0, 1, 2, ..., n-1]代表每个运动员的编号。然后我们对idx排序排序的规则是分数更高的下标排在前面。排序完成后idx[0]就是得分最高的人的下标idx[1]是得分第二高的下标依此类推。接着我们创建一个字符串数组res长度n然后遍历idx把idx[i]处的运动员名次设置成i1对应的描述前三种用奖牌字符串后面的用数字字符串。这样就省掉了一张哈希表节省了内存和哈希运算的开销。具体代码如下class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); vectorint idx(n); iota(idx.begin(), idx.end(), 0); // idx [0, 1, 2, ..., n-1] // 按分数降序对下标排序 sort(idx.begin(), idx.end(), [](int a, int b) { return score[a] score[b]; }); vectorstring res(n); for (int i 0; i n; i) { if (i 0) res[idx[i]] Gold Medal; else if (i 1) res[idx[i]] Silver Medal; else if (i 2) res[idx[i]] Bronze Medal; else res[idx[i]] to_string(i 1); } return res; } };3.3 两种映射方案的对比与选型建议我把两张方案的优劣整理成一份对照表方便大家根据自己的情况选对比维度复制数组 哈希表下标映射法额外空间分数数组 哈希表约 2n下标数组约 n映射查找哈希查找摊还 O(1)直接数组索引O(1)代码可读性思路直接容易理解排序比较函数稍绕内存占用高一些哈希表有额外开销更省适合内存受限环境推荐场景面试讲思路首选追求性能/内存时用我自己在LeetCode上提交时两种写法提交时间相差无几因为n不是特别大的时候哈希表的花费可以忽略。但如果n到了10^5甚至10^6下标映射法的优势就会明显体现出来。平时练习的时候我建议两种都写一遍特别是第二种能帮助你更好地理解“对索引排序”这个技巧它在很多更复杂的问题里都会用到。4. 解法三进阶思路——桶排序实现 O(n)4.1 什么情况下可以突破 O(n log n)刚才说过基于比较的排序下界是O(n log n)但如果我们能利用输入数据的额外信息就可以用非比较排序突破这个下界。最常见的就是桶排序或者计数排序。这道题刷完以后我查了不少讨论区的题解看到有高手在题目给出了score[i]范围的前提下比如分数范围远小于n或者范围是已知有限整数域直接用桶排序把时间复杂度降到了O(n)。这让我想起一个业务里的场景如果成绩都是0到100的整数给几百万人排等级用比较排序就是浪费桶排序才是正解。4.2 桶排序法实现与代码思路很简单先找出分数的最大值maxScore。开辟一个桶数组bucket长度是maxScore 1初始化为 -1。遍历原始数组把bucket[score[i]] i存进去意思是“这个分数对应的运动员下标是 i”。从maxScore往下遍历桶遇到的第一个非空桶就是第一名依次给对应下标设置名次描述。注意分数范围如果特别大比如10^9这个做法就不可行了因为桶数组根本开不出来。所以它的适用前提是分数范围可控。C实现大致长这样class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); if (n 0) return {}; int maxScore *max_element(score.begin(), score.end()); vectorint bucket(maxScore 1, -1); for (int i 0; i n; i) { bucket[score[i]] i; } vectorstring res(n); int rank 1; for (int s maxScore; s 0; s--) { if (bucket[s] ! -1) { int idx bucket[s]; if (rank 1) res[idx] Gold Medal; else if (rank 2) res[idx] Silver Medal; else if (rank 3) res[idx] Bronze Medal; else res[idx] to_string(rank); rank; } } return res; } };4.3 孰优孰劣算法选型的现实考量桶排序在理想情况下是O(n maxScore)如果maxScore跟n同量级那就是O(n)确实快。但代价是空间消耗直接跟分数上限挂钩分数范围到10^7时bucket数组就要开几千万个int约160MB内存这在很多在线评测系统上是过不去的。所以在实际工程或者竞赛里我更推荐从“分治思想”的角度理解桶排序而不是无脑追求这个理论最优。刷题最有价值的不是背下最优解而是看懂每个算法背后的适用边界。桶排序适合“范围小、数据密集”的场景哈希映射适合“通用、稳定、可读性强”的场景对n在10^4量级的本题来说前两个解法已经完全够用。5. 边界情况、踩坑记录与实测体验5.1 分数相同怎么办题目没有明确说明分数是否一定唯一但看很多讨论区以及实际测试数据它并没有像其他题那样保证“score 的所有元素互不相同”。我一开始没注意这个细节直接用分数作为哈希表的 key当时倒也没出问题但后来我脑补了一个场景假设score [100, 100, 50]按照题目规则两个100分到底谁第一谁第二这其实是无法决定的因为题目给的信息不足以构建出唯一的“相对名次”。如果硬要在这种数据上跑哈希表会因为key冲突而丢失映射信息下标数组排序也会因为比较函数返回false而出现未定义的行为排序比较器必须满足严格弱序不然sort会崩或者结果不确定。稳妥的处理方式是要么用stable_sort在分数相同时保留下标顺序要么给每个分数附加一个运动员编号作为联合标识。我自己的做法是先假设测试数据没问题但会把排序的比较函数写成“分数降序分数相同按下标升序”的双关键字形式这样即使出现相等分数也不会翻车。5.2 输出数组的大小写和格式Gold Medal、Silver Medal、Bronze Medal这三个字符串的大小写必须和题目要求完全一致少写一个字母或者大小写写错LeetCode会直接报错。尤其是Medal不是Meddle别问我是怎么知道的。数字名次部分则要从4开始不是1、2、3因为这三个位置被奖牌字符串占了。5.3 排序函数自检时的注意事项在线调试的时候建议先自己在本地构造几组数据跑一遍score [1]只有一个运动员输出应该是[Gold Medal]。score [1, 2]输出应该是[Silver Medal, Gold Medal]。score [5, 4, 3, 2, 1]输出正好和输入顺序一样可以直观检查。乱序的比如[10, 3, 8, 9, 4]根据我前面举的例子输出应该是[Gold Medal, 5, Bronze Medal, Silver Medal, 4]。这四组测完基本上边界覆盖就到位了。5.4 实测提交记录与优化心得我把第一版哈希表解法提交上去以后运行时间大概在十几毫秒左右击败了约90%的提交。随后换成下标映射法时间波动不大但内存占用下降了一点点。后来我尝试在排序比较器里加双关键字逻辑时间几乎没变说明这种规模下差异真的可以忽略不计。值得一提的是我在执行时间最慢的用例上做过一次实验构造n 100000的随机数据哈希表解法的耗时会明显增加因为unordered_map的hash计算和内存分配在大量元素下不是免费的而下标映射法始终很稳定这也是我最终给同事推荐下标映射法的原因。5.5 相关题目的串联与延伸思考“相对名次”这个模型其实不止一道题在考。比如力扣上的“根据数字二进制下1的数目排序”1356题用到了“改造排序规则”的思路“最大数”179题则用到了“自定义排序比较器”的手法。如果你把这个题吃透那么上面这些题的底层思维基本就通了排序规则不一定是自然序完全可以按业务需求定义。对我来说刷题不是比谁记得的答案多而是训练一套可迁移的解题模型。相对名次是“排序 映射”最大数是“排序 拼接规则”你还遇到过哪些类似的场景欢迎在评论区聊聊你的解法。最后说个我自己在实际操作中的体会很多看似简单的题目如果你能坚持写多种解法、分析它们的适用边界、想想真实业务里会怎么变形收获会比盲目刷十道新题更大。这道“相对名次”就是一个不错的练手样本从最笨的暴力法到哈希映射、下标排序、桶排序每往前走一步都能感受到算法思维上的提升。