LeetCode-Go 题解：506. Relative Ranks（相对名次）——map 索引 + 降序排序的 Go 实现

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 位运动员的获奖情况。

输入输出示例

示例 1：

Input: score = [5,4,3,2,1] Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"] Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

分数本身已按降序排列，因此下标 0～4 恰好对应第 1～5 名，前三位直接颁发金银铜牌，后两位输出名次编号。

示例 2：

Input: 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.length
• 1 <= n <= 10000
• 0 <= 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的名次就是i+1（前三位特殊处理为奖牌字符串），再通过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 个元素的名次为i+1，这是后续回填逻辑的基础。sort.Slice底层使用 pdqsort（Go 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)将名次整数转为字符串。注意i+1是因为名次从 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 -covermode=atomic -coverprofile=coverage.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-Go，Go 版本为 1.19，sort.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