LeetCode-Go 题解506. Relative Ranks相对名次——map 索引 降序排序的 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 仓库中 0506.Relative-Ranks 题解 为核心深入讲解第 506 题「Relative Ranks相对名次」的完整解题思路与 Go 实现。你将掌握如何用「哈希表记录原始下标 降序排序」这一经典组合将一维分数数组高效转换为排名字符串数组并了解该解法在仓库中的源码、单元测试与覆盖率验证全貌。一、题目理解将分数数组转换为名次数组第 506 题给定一个长度为 n 的整数数组score其中score[i]是第 i 位运动员在比赛中的得分且所有得分互不相同保证唯一性。运动员根据得分决定名次得分最高者为第 1 名次高者为第 2 名依此类推。名次与获奖情况的映射规则如下第 1 名获得金牌Gold Medal第 2 名获得银牌Silver Medal第 3 名获得铜牌Bronze Medal从第 4 名到第 n 名获得其名次编号对应的字符串第 x 名得到字符串x。最终返回长度为 n 的字符串数组answer其中answer[i]是第 i 位运动员的获奖情况。输入输出示例示例 1Input: score [5,4,3,2,1] Output: [Gold Medal,Silver Medal,Bronze Medal,4,5] Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].分数本身已按降序排列因此下标 04 恰好对应第 15 名前三位直接颁发金银铜牌后两位输出名次编号。示例 2Input: score [10,3,8,9,4] Output: [Gold Medal,5,Bronze Medal,Silver Medal,4] Explanation: The placements are [1st, 5th, 3rd, 2nd, 4th].这个示例更能体现题目的核心难点原始数组中下标 0 的10是最高分第 1 名下标 1 的3却是最低分第 5 名下标 2 的8是第 3 名下标 3 的9是第 2 名下标 4 的4是第 4 名。输出的顺序必须与输入数组的下标保持一致而不是按排名顺序输出。约束条件n score.length1 n 100000 score[i] 1000000数组中所有值互不相同由于分数值域可达 100 万、数组规模可达 1 万且需要同时维护「分数 → 名次」与「原下标 → 名次」两层映射选择合适的数据结构至关重要。二、核心解题思路map 记录下标 降序排序回填原文档给出的解题思路十分精炼用 map 记录原来 score 中元素对应的坐标然后对 score 进行排序对排序后的元素我们通过 map 就可以知道它排的名次了。将其拆解为三个关键步骤即可理解算法全貌第一步建立「分数 → 原始下标」的哈希映射遍历原数组将每个分数v与其原始下标i存入mp[v] i。这一步利用了「所有分数互不相同」的约束——正因为分数唯一mp的键才不会冲突才能保证每个分数唯一地对应一个原始下标。第二步对分数数组原地降序排序通过sort.Slice配合score[i] score[j]的比较器实现降序。排序完成后排序后下标0、1、2、3…恰好对应名次第 1、2、3、4…名。第三步遍历排序后的数组将名次回填到原始下标处排序后第 i 个元素v的名次就是i1前三位特殊处理为奖牌字符串再通过mp[v]找到它原来在数组中的下标写入ans数组的对应位置。整个算法的时间复杂度为 O(n log n)排序主导空间复杂度为 O(n)哈希表与答案数组各占一份。三、Go 完整实现与逐行解读以下是 506.Relative Ranks.go 中的完整源码与 README 文档中的代码完全一致可直接复制运行package leetcode import ( sort strconv ) func findRelativeRanks(score []int) []string { mp : make(map[int]int) for i, v : range score { mp[v] i } sort.Slice(score, func(i, j int) bool { return score[i] score[j] }) ans : make([]string, len(score)) for i, v : range score { if i 0 { ans[mp[v]] Gold Medal } else if i 1 { ans[mp[v]] Silver Medal } else if i 2 { ans[mp[v]] Bronze Medal } else { ans[mp[v]] strconv.Itoa(i 1) } } return ans }关键点逐行解读1. 哈希表mp分数到原始下标的反向索引mp : make(map[int]int) for i, v : range score { mp[v] i }这是整个解法的枢纽。原数组在排序后下标会完全被打乱mp让我们在排序完成后仍然能回答「这个分数原本在哪个位置」。由于题目保证分数唯一mp的键不会发生覆盖。2. 降序排序sort.Slice的比较器sort.Slice(score, func(i, j int) bool { return score[i] score[j] })这里对传入的score原地排序直接修改了原切片。排序后第 i 个元素的名次为i1这是后续回填逻辑的基础。sort.Slice底层使用 pdqsortGo 1.19 起默认的混合排序算法在近乎有序等场景下也有良好表现。3. 前三名特殊处理 其余名次编号if i 0 { ans[mp[v]] Gold Medal } else if i 1 { ans[mp[v]] Silver Medal } else if i 2 { ans[mp[v]] Bronze Medal } else { ans[mp[v]] strconv.Itoa(i 1) }排序后的下标 0、1、2 对应前三名映射为奖牌字符串从下标 3 开始用strconv.Itoa(i 1)将名次整数转为字符串。注意i1是因为名次从 1 开始计数而下标从 0 开始。每一次赋值的目标位置都是ans[mp[v]]即该分数在原数组中的下标从而保证输出顺序与输入顺序一致。算法复杂度时间复杂度O(n log n)。sort.Slice的排序为 O(n log n)两次线性遍历建表与回填均为 O(n)整体由排序主导。空间复杂度O(n)。哈希表mp与答案数组ans各占用 O(n) 空间sort.Slice在部分排序场景下可能有少量额外空间。四、源码、单元测试与覆盖率验证1. 单元测试覆盖两个官方示例仓库为本题提供了专门的测试文件 506.Relative Ranks_test.go采用「参数-答案」结构化的表格驱动风格组织用例type question506 struct { para506 ans506 } // para 是参数 type para506 struct { score []int } // ans 是答案 type ans506 struct { ans []string } func Test_Problem506(t *testing.T) { qs : []question506{ { para506{[]int{5, 4, 3, 2, 1}}, ans506{[]string{Gold Medal, Silver Medal, Bronze Medal, 4, 5}}, }, { para506{[]int{10, 3, 8, 9, 4}}, ans506{[]string{Gold Medal, 5, Bronze Medal, Silver Medal, 4}}, }, } // ... for _, q : range qs { _, p : q.ans506, q.para506 fmt.Printf(【input】:%v 【output】:%v\n, p.score, findRelativeRanks(p.score)) } }用例分别对应 README 中的两个官方示例第一个验证完全降序输入下的直白输出第二个验证乱序输入下「排名与原始下标交错」的关键场景即[10,3,8,9,4]→[Gold Medal,5,Bronze Medal,Silver Medal,4]能够有效检验 map 回填逻辑的正确性。2. 覆盖率佐证100% 行覆盖仓库通过 gotest.sh 统一执行测试并收集覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...在 coverage.txt 中可以找到本题源码的覆盖记录例如github.com/halfrost/LeetCode-Go/leetcode/0506.Relative-Ranks/506.Relative Ranks.go:8.46,10.26 2 2 github.com/halfrost/LeetCode-Go/leetcode/0506.Relative-Ranks/506.Relative Ranks.go:13.40,15.3 1 12 github.com/halfrost/LeetCode-Go/leetcode/0506.Relative-Ranks/506.Relative Ranks.go:20.20,22.4 1 2 github.com/halfrost/LeetCode-Go/leetcode/0506.Relative-Ranks/506.Relative Ranks.go:24.9,26.4 1 4从记录可看出建表循环执行了 10 次对应两个用例共 5 5 个元素、排序调用 2 次、回填循环 10 次三个分支金牌、银牌、铜牌、数字名次均被执行到函数整体达到 100% 行覆盖。3. 在题库总表中的定位仓库根目录 README.md 的题库总表中记录着本题的元信息0506 | Relative Ranks | Easy难度为 Easy且提供了指向本题目录的入口链接。本仓库模块名在 go.mod 中声明为github.com/halfrost/LeetCode-GoGo 版本为 1.19sort.Slice的用法与该项目使用的 Go 版本完全兼容。4. 本地运行验证方式在仓库根目录执行以下命令即可复现测试输出与覆盖率验证# 运行全部测试含本题用例 go test ./leetcode/... # 按 gotest.sh 的方式生成覆盖率文件 bash gotest.sh # 仅运行本题测试并输出用例日志 go test -v -run Test_Problem506 ./leetcode/0506.Relative-Ranks/五、边界情况与扩展思考n 1 时数组只有一个元素排序后i 0直接返回[Gold Medal]代码无需额外特判。分数含 0约束允许score[i] 0。由于mp[0]同样能正常建立映射0 与任意下标都不冲突代码天然兼容无需处理。不修改原数组的替代方案当前实现是对score原地排序若业务要求保留原始分数数组可额外拷贝一份排序或改为对下标切片idx : []int{0,1,...,n-1}按score[idx[i]] score[idx[j]]排序本质思路一致空间开销会略有增加。为什么不用「分数→名次」直接映射若只建score - rank的映射遍历原数组时仍能通过映射得到每个下标的排名这是另一种等价写法可省去回填时的mp[v]查找。本仓库的解法选择先记录原始下标再回填二者的时间复杂度相同都基于「分数唯一」这一前提可结合场景选择。小结第 506 题的核心价值在于训练「索引保序」思维当排序会破坏元素与位置的对应关系时先用哈希表建立反向索引排序后再按需回填即可用 O(n log n) 的时间、O(n) 的空间干净利落地解决。通过阅读本题的 题解文档、源码 与 测试你可以完整掌握这一模式并将其迁移到「排名、Top-K、按值恢复原序」等更广泛的 LeetCode 问题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
