上周我在刷题群里看到一个很有意思的提问做LeetCode 506题相对名次时为什么直接把分数从大到小排序后返回输出结果跟预期完全对不上底下一堆人回复“因为要保持原数组顺序啊”但提问者还是不理解。其实这道题在LeetCode里被标记为简单题真正卡住人的往往不是排序本身而是“如何把排名结果映射回原来的位置”。今天借着这个题目把哈希映射、下标排序、复杂度分析、边界检查这些点一次讲清楚顺便把我踩过的坑也一并交代。如果你正准备面试或者刚开始刷题这道题非常适合用来理解“排序之后如何回填原位置”这一类问题的通用套路。1. 先别急着写代码把506题的输入输出和隐藏约束看透1.1 题面在说什么以及最常见的误读是什么LeetCode 506题的英文名是Relative Ranks中文一般翻译成“相对名次”。题面给你一个整数数组scorescore的长度为n每个元素是一名运动员的得分。要求返回一个同样长度为n的字符串数组数组中第i个元素表示第i名运动员的名次。前三名有特殊待遇分别要返回Gold Medal、Silver Medal、Bronze Medal也就是金、银、铜牌。从第四名开始直接返回数字字符串比如第4名返回4第5名返回5以此类推。很多第一次做这道题的人会把“相对名次”误解成“把分数排名后按名次顺序输出”。比如输入是[5, 4, 3, 2, 1]正确输出是[Gold Medal, Silver Medal, Bronze Medal, 4, 5]因为原数组第0位是5分最高分给金牌第1位是4分给银牌第2位是3分给铜牌第3位是2分是总排名第4所以返回4第4位是1分总排名第5所以返回5。但有人会把数组排序成[1, 2, 3, 4, 5]之后直接返回[5, 4, Bronze Medal, Silver Medal, Gold Medal]这其实是按名次顺序而不是按原数组顺序输出了题目要求的是保持原始输入顺序。这个误读非常普遍也是这个题第一个隐藏的知识点结果数组的索引必须和原数组索引一一对应排序只是为了得到排名不能破坏原数组结构。1.2 边界条件哪些细节决定了你是不是白写一场这道题看似简单边界条件其实有不少稍不注意就是一次错误提交。第一个边界是n的最小值。题目约束中n至少为1。当n等于1时只有一个运动员他既是第一名也是唯一的金牌得主所以应该返回[Gold Medal]。很多人在写代码时习惯性从第3名之后开始处理但没考虑到n1时数组长度如果代码里写死了“下标从0到2是奖牌”而后面没有兜底倒也不会出错。但要小心的是如果先给奖牌列表分配三个位置再读取可能超出数组范围。第二个边界是分数可以相同吗这道题的约束是“所有分数保证互不相同”这是非常重要的一点。正因为分数不重复才可以放心地用分数作为哈希表的key。如果分数重复一个key就会对应多个运动员那就要用更复杂的索引排序方案来处理。很多扩展题正是从这里挖坑的所以这个约束一定要在审题时看到。第三个边界是结果类型。题目要求返回字符串数组而不是数字数组。前三名要用特定的英文字符串第四名及以后要把整数名次转换成字符串。这里最容易出的低级错误是返回了List 或者把4写成了4th这些都属于没有认真看返回类型。第四个边界是分数范围。分数可能是0也可能是很大的整数但排序时不需要关心具体大小只关心相对关系。分数的绝对值不影响算法所以这道题的时间复杂度和数值范围无关。1.3 刷题第一反应为什么“排序-对应-填回”是自然思路如果你拿到这题第一反应可能是“先排序再根据排名输出”。这个思路方向是对的但缺少了一个关键环排序之后你怎么知道原来某个位置的分数排第几假设输入是[10, 30, 20]排完序是[30, 20, 10]对应名次是第1、第2、第3。现在你要填回原数组的answer[0]时得知道10分排第几。如果不额外记录就得再遍历一遍排序后的数组寻找10分所在位置。对每个原数组元素都做一次线性查找整体时间复杂度就变成了O(n²)。这是最直观但又最糟糕的做法。更聪明的做法是建立一个“分数 - 名次”的映射关系。排序之后按顺序遍历排序结果把每个分数和它对应的名次存进哈希表。然后遍历原数组每个元素直接查哈希表O(1)时间就能拿到名次。这就是这道题的核心知识点哈希映射用空间换时间。所以这道题其实考察了两件事第一你是否知道排序后需要保持原数组顺序第二你是否会用哈希表来快速建立排序结果和原数组元素的对应关系。2. 哈希映射解法最省脑子的工程化写法2.1 排序后的分数怎么和原数组扯上关系我们来把“排序-对应-填回”这个思路落地成具体的算法步骤。第一步复制原数组并降序排序。排序结果是第0名是最高分第1名是次高分第2名是第三高分。第二步建立一个空哈希表。遍历排序后的数组下标i就代表排名。如果i等于0说明是第一名在哈希表里记录当前分数 - Gold Medal。i等于1记录当前分数 - Silver Medal。i等于2记录当前分数 - Bronze Medal。i大于等于3时记录当前分数 - 字符串形式的排名也就是str(i 1)。第三步遍历原数组中的每个分数用score[i]作为key去哈希表里查对应名次然后放进结果数组。为什么用哈希表因为这里需要快速查找。如果不用哈希表每查一个分都要遍历一遍排序后的数组数据一旦到几千上万个就会明显变慢。哈希表的平均查询是O(1)虽然排序要多花O(n log n)但整体算法依然是高效的。这里还有一个小细节一定要复制原数组再进行排序不能直接对原数组排序。因为最后一步还要按照原数组顺序输出如果原数组被排成降序你就丢了原本的位置信息。我的做法是使用sorted(score, reverseTrue)创建一个新列表这样原数组不会被污染。2.2 完整代码与逐行拆解Python为例直接给一份可以提交的Python代码class Solution: def findRelativeRanks(self, score: List[int]) - List[str]: # 1. 降序排序分数排序后下标i就是排名-1 sorted_scores sorted(score, reverseTrue) # 2. 建立分数到名次的映射 rank_map {} for i, s in enumerate(sorted_scores): if i 0: rank_map[s] Gold Medal elif i 1: rank_map[s] Silver Medal elif i 2: rank_map[s] Bronze Medal else: rank_map[s] str(i 1) # 3. 按原数组顺序查询并生成结果 return [rank_map[s] for s in score]逐行解释一下。sorted(score, reverseTrue)会返回一个新的降序列表原score不变。这里一定要记住不能用score.sort(reverseTrue)因为那会修改原数组导致最后一步失去原始顺序。enumerate(sorted_scores)在循环里同时拿到下标和值。i等于0时s是最高分所以把s映射到Gold Medal。i等于1时映射到Silver Medali等于2时映射到Bronze Medal。从i等于3开始实际的排名是i1比如i3对应第4名所以存str(i 1)而不是str(i)这是最容易犯错的地方。最后一行是列表推导式遍历原数组里的每个分数从rank_map里查出名次字符串。因为题目保证分数互不相同所以每个分数在rank_map里只有一个对应值不会出现重复key覆盖的问题。如果换成Java思路完全一样只是map的写法不同class Solution { public String[] findRelativeRanks(int[] score) { int n score.length; int[] sorted score.clone(); Arrays.sort(sorted); MapInteger, String map new HashMap(); for (int i n - 1; i 0; i--) { if (i n - 1) { map.put(sorted[i], Gold Medal); } else if (i n - 2) { map.put(sorted[i], Silver Medal); } else if (i n - 3) { map.put(sorted[i], Bronze Medal); } else { map.put(sorted[i], String.valueOf(n - i)); } } String[] res new String[n]; for (int i 0; i n; i) { res[i] map.get(score[i]); } return res; } }Java这里有个小技巧用Arrays.sort默认升序排序所以排序后最后一个元素是最高分。倒着遍历反而方便i从n-1到0分别对应第1名到第n名。这个方向上的处理思路和Python不同但本质一样都是先得到名次再建映射。2.3 复杂度和空间占用这笔账怎么算时间复杂度上排序是O(n log n)建哈希表是O(n)最后遍历原数组也是O(n)所以整体是O(n log n)。空间复杂度呢sorted_scores占O(n)rank_map最多存n个键值对占O(n)结果数组本身就是题目要的输出通常不计入额外空间但严格来说它也要O(n)。所以额外空间是O(n)。为什么不是O(1)如果你用排序再怎么省排序本身也需要O(log n)到O(n)的递归栈或临时空间。再加上哈希表空间就是O(n)。这个复杂度对于n在10的4次方量级的数据来说完全没问题。我记得这道题在LeetCode上的n上限是10^4也就是一万个运动员O(n log n)跑起来是毫秒级基本没有性能压力。这里要特别说一句哈希映射方案虽然空间占用多一些但它的思路最简单、最不容易写错。面试时如果时间紧张第一优先写这个方案。空间换时间在这个量级下非常划算。3. 下标排序解法用索引换掉哈希表3.1 核心思想不存分数名次而是给下标排个序哈希映射方案虽然好理解但有些人会问能不能不用哈希表省掉那个O(n)的空间答案是能做法是对下标排序。这个思路比较巧妙我们真正关心的是“原数组里第i个位置的运动员他的分数排在所有分数中的第几名”。如果把所有下标0到n-1拿出来按照这些下标对应的分数进行降序排序那么排序后的第一个下标就对应最高分第二个下标对应次高分以此类推。这样可以直接通过下标找到原数组中的位置把名次字符串填进结果数组。举个例子score [10, 30, 20]下标数组是[0, 1, 2]。按照score[0]10、score[1]30、score[2]20降序排序得到[1, 2, 0]。现在遍历这个排好序的下标数组第一个下标是1说明原数组下标1的位置是冠军所以ans[1]填Gold Medal第二个下标是2ans[2]填Silver Medal第三个下标是0ans[0]填Bronze Medal。最终结果就是[Bronze Medal, Gold Medal, Silver Medal]和哈希映射方案得到的结果一致。这种做法的核心在于排序的对象不是分数而是下标。每个下标唯一指向原数组的一个位置不会丢失原始顺序信息。3.2 代码实现Python和Java的常见写法差异Python实现下标排序非常优雅因为可以用sorted配合key参数直接对range(n)排序class Solution: def findRelativeRanks(self, score: List[int]) - List[str]: n len(score) # 对下标排序按分数降序 indices sorted(range(n), keylambda i: -score[i]) ans [] * n medals [Gold Medal, Silver Medal, Bronze Medal] for rank, idx in enumerate(indices): if rank 3: ans[idx] medals[rank] else: ans[idx] str(rank 1) return ans这里sorted(range(n), keylambda i: -score[i])的意思是对0到n-1这些下标排序排序的规则是每个下标对应的分数的相反数。取负号是为了让高分排在前面因为默认是升序负一下大的变成小的也就排到前面了。也可以用keylambda i: score[i], reverseTrue效果一样。medals [Gold Medal, Silver Medal, Bronze Medal]用一个数组存奖牌字符串方便后面按rank直接取。rank从0开始正好对应奖牌数组的下标所以rank 3时medals[rank]就能拿到对应的奖牌字符串。这个写法比三个if else要简洁许多而且不容易漏。Java的话因为基本类型数组没法直接用自定义Comparator需要先把Integer[]或int[]转换成Integer[]或者使用Java 8的Stream。一个比较干净的写法是class Solution { public String[] findRelativeRanks(int[] score) { int n score.length; Integer[] idx new Integer[n]; for (int i 0; i n; i) idx[i] i; Arrays.sort(idx, (a, b) - score[b] - score[a]); String[] ans new String[n]; String[] medals {Gold Medal, Silver Medal, Bronze Medal}; for (int rank 0; rank n; rank) { int originIndex idx[rank]; if (rank 3) { ans[originIndex] medals[rank]; } else { ans[originIndex] String.valueOf(rank 1); } } return ans; } }注意Java的Comparator不能直接对基本类型数组用所以要先装箱成Integer[]。另外score[b] - score[a]这种写法在这个场景下没问题因为分数差值不大时不会溢出但严格来说更安全的是Integer.compare(score[b], score[a])。这道题分数范围不大用减法可以但如果是工程代码建议用Integer.compare避免极端情况下的整数溢出。3.3 两种解法对比时间差不多但使用场景不同我们用一个表格来看哈希映射和下标排序的差别维度哈希映射解法下标排序解法核心数据结构哈希表分数-名次下标数组额外空间sorted数组 HashMap约O(n) 两倍于n下标数组约O(n) 一倍于n时间复杂度O(n log n)O(n log n)理解难度直观适合新手稍微绕但代码可复用性高分数重复时会覆盖不适用可以配合稳定排序处理面试表达先答这个再提下标排序作为优化展示你对排序本质的理解实际使用中哈希映射方案更保险不容易在排序比较器上出错。下标排序方案在分数重复时更有优势因为可以对下标按分数排序然后进一步处理并列情况。但这不是LeetCode 506题的考点属于延伸思考。如果你面试时写出哈希映射方案面试官大概率会追问一句“能不能不用额外哈希表”这时候再给出下标排序方案比一开始就写显然更有加分效果。这个“先基础、再优化”的节奏是刷题面试中比较讨喜的。4. 躲开这些坑运行效率和使用体验会好很多4.1 原数组顺序被改掉的经典事故这道题最大的坑就是不小心修改了原数组。很多人会写score.sort(reverseTrue) # 然后遍历score构建结果这样做会直接让原数组变成降序排列后续你压根不知道原来的第0个元素是谁。结果数组的顺序会完全错乱。虽然题目没有明确说“不能修改原数组”但返回值要求对应原数组下标所以原数组是你唯一的顺序依据绝不能动。我在实际写的时候会把“复制一份用来排序”和“原数组用来查位置”这两件事在代码注释里写清楚避免半天之后回头看不知道自己为啥要复制。这个习惯在工程里也很重要函数入参不要轻易修改除非题目明确要求原地操作。4.2 分数重复时哈希表会悄悄覆盖为什么题目说不需要担心刚才我们反复提到题目保证分数互不相同。怎么理解这个保证它意味着你可以放心用分数作为哈希表的key。如果分数相同比如有两个100分排序后第一个100分记录为第1名第二个100分也会试图记录同样的key哈希表就会把原来的第1名覆盖成第2名。这样两个100分运动员映射到的名次都变成了第2名结果就错了。在LeetCode 506题里这个情况不会发生所以哈希表方案安全。但面试官经常把这道题改成“分数可能并列”让你重新设计。这时就要用到下标排序的方案而且还要定义并列规则比如相同分数按原数组顺序排或者相同分数给相同名次。这些属于扩展题但你要是能现场说出来绝对是加分项。我自己的习惯是遇到“互不相同”这种约束先想想它到底帮我们省了什么。如果完全没意识到它省掉了重复key的覆盖问题说明还没有真正理解哈希表方案的适用前提。4.3 字符串转换、边界n值和其他语言细节第四名及以后要把整数名次转成字符串。Python里用str(rank 1)Java里用String.valueOf(rank 1)C里用to_string(rank 1)。这个转换本身简单但容易错在索引偏移上。比如你遍历排序后的数组下标i从0开始第i个元素实际上是第i1名所以转换时是i1来转不是i。这是我见过最多的低级错误之一。n等于1或者2的时候代码也要正确。n2时两个分数分别是冠军和亚军没有季军。不管是哈希映射还是下标排序只要在循环里判断rank 3就不会把第三名硬塞给一个不存在的人。哈希映射方案里排序后数组长度为2循环到i1就结束了也不会错误地给第2名存一个Bronze Medal。还有一个小细节返回数组初始化。有些语言里字符串数组默认值是null如果你忘了给所有位置赋值最后输出会发现一堆null。下标排序方案中ans [] * n 这种初始化要记得写。我见过有人初始化了String[n]但漏了填充结果前几个奖牌位置是null被LeetCode判了执行错误。最后一个容易被忽略的是如果分数值很大比如10的9次方用负数取反-score[i]不存在溢出问题在Python里没有整数溢出随便写。在Java里如果用score[b] - score[a]减法比较当两个分数差值超过int范围时会有溢出风险。这道题范围小没事但面试时提到用Integer.compare会更专业。5. 从一道简单题看排名类问题的通用解法5.1 三种常见的排名变体以及506题属于哪一种LeetCode 506题其实属于一个很常见的题目家族给定一组元素要求按照某种规则排序后把排名信息映射回原数组。我从刷题和面试中总结出三种变体。第一种是“按原顺序输出排名”就是506题这种。排序后要知道每个原位置的元素在整体中的名次核心做法是建“元素值 - 名次”的映射或者对下标排序。第二种是“输出前K个元素”或“第K大的元素”比如只需要找到前三名分数而不需要为所有元素生成名次。这种题常用的手段是维护一个大小为K的最小堆或者用快速选择算法。与506的区别在于不需要完整排名。第三种是“按排名重新排列原数组”比如给一个数组让你按分数从高到低输出运动员名字。这种题直接对原数组排序即可不需要回填原位置。很多新手会把506题误以为成这种类型实际上506要求的是保持原顺序而这类题并不要求。这三种变体在面试中经常被组合起来考。能一眼看出“这题是506的变体”对控场非常有帮助。5.2 由“分数-名次”映射推广出来的刷题常见套路“建立映射然后按原顺序查询”这个套路不光能解506题在很多场景下都适用。比如根据身高重新排队、根据成绩输出等级、根据ID输出昵称只要是“先全局排序再按原顺序回填”的类型思路完全一样。具体来说套路分三步第一步确定排序对象和排序规则第二步把排序结果保存成便于查询的结构哈希表或下标数组第三步遍历原数据查询并构造输出。这个三步法我在刷题时反复使用遇到相关题目先套这个框架再根据细节调整。比如有一类题是“给定一个数组返回每个元素右边比它小的元素个数”虽然额外用到了一些树状结构但基础思路里也包含了排序后下标映射的影子。明白了506题为什么需要映射再看这类题就不会觉得那么莫名其妙了。5.3 想验证自己真会了做一轮这样的自测在你看完这篇文章之后我建议你别急着关掉拿几个测试用例自己手写一遍。第一个用例是最简单的score [1]输出应该是[Gold Medal]。这能测试n1边界。第二个用例是[1, 2, 3]输出应该是[Bronze Medal, Silver Medal, Gold Medal]。注意原数组顺序是升序但是名次要倒着给。第三个用例是[7, 3, 5, 1]对应排名7最高其次是5、3、1所以输出是[Gold Medal, Bronze Medal, Silver Medal, 4]。这个用例能测试你是否真的按照分数大小而不是数组顺序来定名次。第四个用例是[1, 2, 3, 4, 5]输出[5, 4, Bronze Medal, Silver Medal, Gold Medal]。很多人在这个用例上会搞混金牌和银牌的位置。如果在纸上推导这些用例时每一步能说出“现在是第几名对应原数组哪个位置”那说明你已经掌握了这道题最核心的思维。代码能不能一次跑通反而不那么重要重要的是你的思维链路是清晰的。最后再分享一个我自己的习惯每次做完一个简单题我会强迫自己用至少两种不同的方法重新实现一遍。学506题的时候先用哈希映射再用下标排序两者都跑通之后我才觉得这道题真正吃透了。这个方法听起来笨但对打基础真的很有效尤其适合刚刷题不久的朋友。