LeetCode 506 相对名次（简单）题解：排序定名次、哈希映射还原顺序的模拟解法

教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇题解基于「刷穿 LeetCode」系列中 506. 相对名次简单 一文展开完整讲解如何借助「排序 模拟」在 $O(n\log{n})$ 时间内为互不相同的比赛得分生成金、银、铜牌与数字名次并补充多语言实现、边界细节与仓库内同类题型索引读完即可独立写出可提交的完整解法。题目回顾按得分高低决定获奖情况这是 LeetCode 上的506. 相对名次难度为简单Tag 为「排序」、「模拟」仓库中同主题索引见 Index/排序.md 与 Index/模拟.md。题目给出一支长度为n的整数数组score其中score[i]是第i位运动员的比赛得分且所有得分互不相同。运动员根据得分高低决定名次得分最高者名次第1获金牌Gold Medal名次第2的运动员获银牌Silver Medal名次第3的运动员获铜牌Bronze Medal从名次第4到第n的运动员只能获得他们的名次编号字符串名次第x的运动员获得x。最终需要用长度为n的数组answer返回获奖情况其中answer[i]是第i位运动员保持原输入顺序的获奖情况。示例 1输入score [5,4,3,2,1] 输出[Gold Medal,Silver Medal,Bronze Medal,4,5] 解释名次为 [1st, 2nd, 3rd, 4th, 5th] 。示例 2输入score [10,3,8,9,4] 输出[Gold Medal,5,Bronze Medal,Silver Medal,4] 解释名次为 [1st, 5th, 3rd, 2nd, 4th] 。数据范围提示n score.length1 n 10^40 score[i] 10^6score中的所有值互不相同核心思路排序定名次哈希表还原顺序题目的难点在于名次依据分数高低确定但答案要求按原始数组下标顺序输出即第i位运动员对应score[i]的名次。直接对score排序会丢失“谁是谁”的信息因此需要借助辅助结构保留映射关系。解法分三步对应原文档中的「模拟」解法拷贝并排序先对score数组进行拷贝得到clone再对clone升序排序。拷贝的意义在于不破坏原始数组的顺序信息排序后的clone天然形成了分数 → 名次的一一对应关系。建立分数 → 名次映射利用“所有得分互不相同”这一关键性质从高分到低分遍历排序数组将每个分数与名次存入哈希表。遍历时下标i从n - 1递减到0则clone[i]的名次为n - 1 - i最大分数对应名次0次大对应1依此类推。这里名次用0起始的编号是为了方便直接用下标访问金银铜牌字符串数组。构造答案再次遍历原始score对每个分数从哈希表中取出其名次编号rank若rank 3即第 1、2、3 名直接使用预先定义好的{Gold Medal, Silver Medal, Bronze Medal}字符串数组对应元素否则将rank 1转为字符串作为数字名次因为哈希表中的编号是0起始的实际名次要1。其中步骤 2 与步骤 3 各用一次 $O(n)$ 遍历即可完成排序是整体复杂度的主导项。代码实现Java原文档解法class Solution { String[] ss new String[]{Gold Medal, Silver Medal, Bronze Medal}; public String[] findRelativeRanks(int[] score) { int n score.length; String[] ans new String[n]; int[] clone score.clone(); Arrays.sort(clone); MapInteger, Integer map new HashMap(); for (int i n - 1; i 0; i--) map.put(clone[i], n - 1 - i); for (int i 0; i n; i) { int rank map.get(score[i]); ans[i] rank 3 ? ss[rank] : String.valueOf(rank 1); } return ans; } }实现细节说明score.clone()生成拷贝数组原数组score后续遍历时下标顺序不受排序影响金牌、银牌、铜牌名称被提取为类成员数组ss通过rank 3 ? ss[rank] : ...一次三元判断完成特殊名次的字符串映射逻辑紧凑数字名次使用String.valueOf(rank 1)注意与哈希表中0起始编号的换算关系避免出现名次整体错位。C 实现同思路扩展class Solution { public: vectorstring findRelativeRanks(vectorint score) { int n score.size(); vectorstring ans(n); vectorint clone score; sort(clone.begin(), clone.end(), greaterint()); unordered_mapint, int map; for (int i 0; i n; i) map[clone[i]] i; vectorstring medal {Gold Medal, Silver Medal, Bronze Medal}; for (int i 0; i n; i) { int rank map[score[i]]; ans[i] rank 3 ? medal[rank] : to_string(rank 1); } return ans; } };C 版本采用降序排序greaterint()排序后下标i直接就是0起始的名次编号逻辑上更直观也可沿用原文档的升序写法用n - 1 - i换算名次。Python 实现同思路扩展class Solution: def findRelativeRanks(self, score: List[int]) - List[str]: n len(score) clone sorted(score, reverseTrue) rank_map {val: i for i, val in enumerate(clone)} medal [Gold Medal, Silver Medal, Bronze Medal] return [medal[rank_map[s]] if rank_map[s] 3 else str(rank_map[s] 1) for s in score]Python 通过字典推导式一行完成“分数 → 名次”映射再以列表推导式按原顺序构造答案与 Java 版的三步流程完全对应。TypeScript 实现同思路扩展function findRelativeRanks(score: number[]): string[] { const n score.length const clone [...score].sort((a, b) b - a) const map new Mapnumber, number() for (let i 0; i n; i) map.set(clone[i], i) const medal [Gold Medal, Silver Medal, Bronze Medal] const ans: string[] [] for (let i 0; i n; i) { const rank map.get(score[i])! ans.push(rank 3 ? medal[rank] : String(rank 1)) } return ans }使用扩展运算符[...score]拷贝数组后降序排序其余逻辑与 Java 版一致。复杂度分析时间复杂度$O(n\log{n})$。其中拷贝score数组为 $O(n)$对拷贝数组排序为 $O(n\log{n})$构造哈希表为 $O(n)$利用哈希表构造答案为 $O(n)$。整体复杂度由排序主导为 $O(n\log{n})$。空间复杂度$O(n)$。拷贝数组与哈希表均需要与输入规模线性相关的额外空间答案数组ans为返回结果不计入额外空间开销。在n 10^4的数据范围下$O(n\log{n})$ 的排序方案性能充裕运行时间与内存占用均远低于题目隐含限制。边界情况与易错点n 1的单选手场景只有一个分数时排序与映射只有一项答案固定为[Gold Medal]上述实现无需特判即可正确处理。分数可为00 score[i] 10^6说明最低分可以是0。哈希表以分数为键0同样作为正常键处理无需额外排除。名次编号的偏移若采用升序排序从高分到低分编号时务必使用n - 1 - i换算若采用降序排序则下标即编号。两种写法混用会导致名次整体偏移1位是最常见的出错点。前 3 名的特殊字符串数字名次从4开始判断条件是rank 3即哈希编号3对应实际第4名边界写错会把第4名误判进奖牌区。同类题型延伸仓库中的“排序 哈希/模拟”家族本题是“按值排序后还原原始位置信息”这类题型的代表仓库中还有多道同思路题目可供巩固数组序号转换简单同样的“拷贝 → 排序 → 哈希映射 → 还原”四步流程且需处理重复元素共享同一序号的情况与本题形成对照本题靠“得分互不相同”免去了去重逻辑第三大的数中等同样是求名次类问题但只关心第 3 大可尝试排序 去重或一次遍历的多指针写法高度检查器简单拷贝排序后与原始数组逐位比对统计“错位”个数是“排序结果与原顺序对照”的典型应用根据身高重建队列中等在排序基础上进一步引入贪心插入展示排序类问题的进阶组合按照频率将数组升序排序简单将“计数 排序”结合用自定义比较器按频率与数值双重规则排序。小结LeetCode 506「相对名次」是一道典型的“排序 模拟”入门题先排序建立全局名次序再用哈希表记录“分数 → 名次”的映射最后按原数组顺序还原答案。核心要点有三——拷贝保序、哈希还原、奖牌区边界判断。掌握这一套路后可顺势攻克仓库中 1331、1051、406 等同类题目形成对“排序 映射”题型的系统化认知。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0506「相对名次」题解 —— 排序、哈希映射与优先队列实战AlgoNote 算法通关手册LeetCode 0506「相对名次」题解 —— 排序、哈希映射与优先队列实战 本篇题解基于 AlgoNote 仓库的 相对名次教程文档知识库LeetCode-Go 题解506. Relative Ranks相对名次——map 索引 降序排序的 Go 实现LeetCode Go 题解506. Relative Ranks相对名次——map 索引 降序排序的 Go 实现 本篇文章以 LeetCode Go示例工程LeetCode 846 Hand of Straights一手顺子四策略题解排序、堆、有序映射与哈希表LeetCode 846 Hand of Straights一手顺子四策略题解排序、堆、有序映射与哈希表 导读 本篇基于 leetcode1/leetco示例工程教程上一篇终极指南5分钟快速安装Catppuccin主题打造完美Neovim开发环境下一篇GSL终极指南为什么这个免费科学计算库是科研人员的最爱创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考