1. 从“相对名次”这道LeetCode简单题看清排序题的隐藏考点2021年12月2日的每日一题碰上的是506这道“相对名次”。题面很直白给你一个整数数组scorescore[i]是第i名运动员的得分所有得分互不相同要求返回一个字符串数组answeranswer[i]表示第i名运动员的名次。第一名是“Gold Medal”第二名是“Silver Medal”第三名是“Bronze Medal”从第四名开始直接返回数字字符串比如“4”“5”“6”。这道题在LeetCode上被标为简单题。说实话第一次看到题目描述我脑子里冒出来的第一个想法是这不就是把分数排个序然后按顺序发奖牌嘛。但真正动手写的时候才发现这个“简单题”里藏着好几个容易翻车的细节尤其是“排序后会丢失原始下标”这个问题。很多刷题新手会在这里卡住要么排序后不知道该怎么把名次填回原数组要么为了找回下标写出一堆难看的代码。这题适合谁我觉得三类人都值得做一遍刚接触算法题、正在建立排序解题框架的人准备面试、想复习“排序 索引恢复”这个经典套路的人以及在职场上偶尔要处理“按成绩/得分排名并回填展示需求”的开发同学。题目本身不难但背后延伸出去的思维模型不少下面我按自己的复盘过程来拆。2. 核心思路拆解排序后怎么找回原始下标才是真正的考点2.1 先读懂题目的输入输出关系假设score [10, 3, 8, 9, 4]五个运动员的下标分别是0、1、2、3、4。得分最高的是下标0的10分所以answer[0] “Gold Medal”第二高的是下标3的9分answer[3] “Silver Medal”第三高的是下标2的8分answer[2] “Bronze Medal”剩下下标4的4分排第四answer[4] “4”下标1的3分排第五answer[1] “5”。最后返回[Gold Medal, 5, Bronze Medal, Silver Medal, 4]。这里最关键的点在于名次是按得分从高到低排列的但输出必须回到原始数组的每个下标的对应位置。如果直接对score做排序比如排成[10, 9, 8, 4, 3]你得到了一个降序列表却不知道10分是原来哪个下标的9分是原来哪个下标的。所有后续的“回填”都会变得很别扭。所以解题的命门是排序的“参照物”要带着原始下标一起走。2.2 思路一先排序再用HashMap记录每个分数的名次最直观的方案是复制一份得分数组对复制体做降序排序。排序后遍历这个有序数组用一个HashMap把“得分 - 名次”存下来。最后遍历原始score数组去map里查每个得分对应什么名次填入answer。这个思路很符合第一直觉先建立“分数到名次”的映射再原路走一遍。优点是容易理解代码写起来也顺。缺点是多了个哈希表的开销而且在Java里HashMap会涉及Integer的自动装箱和hash计算虽然这题数据量不大性能上没压力但实现起来有一种“绕了一圈”的感觉。代码大概是下面这个样子public String[] findRelativeRanks(int[] score) { int n score.length; int[] sorted score.clone(); Arrays.sort(sorted); MapInteger, String rankMap new HashMap(); for (int i n - 1; i 0; i--) { if (i n - 1) { rankMap.put(sorted[i], Gold Medal); } else if (i n - 2) { rankMap.put(sorted[i], Silver Medal); } else if (i n - 3) { rankMap.put(sorted[i], Bronze Medal); } else { rankMap.put(sorted[i], String.valueOf(n - i)); } } String[] ans new String[n]; for (int i 0; i n; i) { ans[i] rankMap.get(score[i]); } return ans; }因为Java默认的Arrays.sort是升序排序所以从后往前遍历第一个取到的就是最高分。n - i这个公式正好表示名次i从n-1开始n - (n - 1) 1in-2时n - (n-2) 2以此类推正好对应第1名、第2名。这里有个小坑如果直接用for循环里的i来算名次很多人写成了n - i却忘了加1或者忘了处理前三名调试时反复在边界上撞车。后面我会专门讲这些问题。2.3 思路二对索引数组排序从根上避免丢下标推荐既然问题的核心是“排序后不知道原始下标”那能不能让“原始下标”本身就是排序的对象可以。构造一个Integer[] index数组里面装0、1、2、…、n - 1用自定义比较器按照score[index[i]]的大小对index数组排序。排序后index[0]就是得分最高的原始下标index[1]是第二高的原始下标。直接遍历index数组依次填入Gold Medal、Silver Medal、Bronze Medal和数字名次。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]; for (int i 0; i n; i) { if (i 0) { ans[idx[i]] Gold Medal; } else if (i 1) { ans[idx[i]] Silver Medal; } else if (i 2) { ans[idx[i]] Bronze Medal; } else { ans[idx[i]] String.valueOf(i 1); } } return ans; }这段代码的精髓在于排序的对象不是分数本身而是“下标清单”。分数只是比较时的参照物。排序完成之后idx数组自带了一个信息排在第i位的是原始下标为idx[i]的运动员。这样回填答案时直接ans[idx[i]] 对应名次一步到位不需要哈希表也不需要clone数组。第一次看到这个写法的人可能会觉得别扭为什么要用一个Integer[]而不是int[]因为在Java里Arrays.sort只有针对对象数组的重载版本才支持自定义Comparatorint[]只能按自然顺序排没法降序排。想自定义比较器就得用Integer[]。2.4 为什么不能直接对原数组排序这题最容易出的错误就是“先排序原数组再直接从前往后发奖牌”。比如Arrays.sort(score);排完之后数组里确实是从小到大或从大到小的顺序但你丢失了“每个分数原本属于哪个下标”的信息后面想构建answer数组时你根本不知道answer[某个原始下标]该填什么。有人可能会说那我再找一下每个分数在排序后的位置这其实就是退回了O(n^2)遍历不仅笨而且很容易处理不好重复值本题说得分互不相同还好万一有重复就彻底乱了。所以无论采用哪种解法“带着原始身份去排序”或“排序后再建立映射”是绕不开的关键点。3. 完整实现详解代码逐步拆开看每个细节都讲透3.1 为什么用“分数差”作为比较器有风险在上面的索引数组排序里比较器写的是(score[b] - score[a])这在高性能要求下很常见也很简洁。但很多教科书和面试官会追问一个问题如果score[b] - score[a]整型溢出怎么办这题里score[i]的范围是0到10^6两个分数的差值最多也就是10^6远小于int上限21亿所以不会溢出。但万一题目改一下分数范围变成int的正负极值两个大数相减就可能溢出导致错乱。稳妥的写法是用Integer.compare(score[b], score[a])它的内部实现是大于、小于、等于三个分支比较不会做减法没有溢出风险。我个人建议刷题时如果数据范围明确安全用减法写法简洁没问题但写进简历项目或面试手写时优先用Integer.compare显得更严谨。还可以写成Arrays.sort(idx, (a, b) - Integer.compare(score[b], score[a]));代码可读性更好也不至于被面试官抓到“这里可能溢出”的小尾巴。3.2 主循环里前三名的处理顺序有没有更优雅的写法主循环里我写了if、else if、else if、else四段把前三名和其他名次分开处理。有人觉得啰嗦想用一个String数组存奖牌名然后用i 3去判断String[] medals {Gold Medal, Silver Medal, Bronze Medal}; for (int i 0; i n; i) { ans[idx[i]] i 3 ? medals[i] : String.valueOf(i 1); }这种写法确实更简洁但要注意medals数组的下标正好是0、1、2分别对应第一名、第二名、第三名刚好和i对应。如果选手人数少于3人例如n 1循环只执行一次i 0取medals[0]没问题。n 2时取Gold Medal和Silver Medal也没问题。所以三目运算的写法非常安全。不过很多公司笔试环境里代码的“显式可读性”比“短”更重要。四段if写法一眼就能看清楚边界逻辑三目写法虽然短但容易让人在“i 3”这个条件上顿一下。我个人在刷题时用三目写法比较多在写业务代码时用if分支比较多看场景取舍。3.3 数字名次为什么要用String.valueOf从第四名开始名次要转成字符串。很多人直接写ans[idx[i]] (i 1) 这在Java里也能工作因为字符串拼接会自动把整数转成字符串。但要注意如果这个代码段在循环里被频繁执行拼接会创建额外的StringBuilder对象虽然现代JIT会做优化但写代码时养成用String.valueOf的习惯更干净。其实本题的n不超过一万两种写法性能没有任何肉眼可见的差别。审美上的选择而已。但用String.valueOf至少不会让读者疑惑“是不是在拼接字符串”语义更明确。3.4 桶排序做法知道即可别当主方案因为score[i]范围固定是0到10^6还可以用“计数 倒序扫描”的桶思路来做。开一个长度为maxScore 1的数组bucketbucket[score[i]] i记录每个分数对应的原始下标。然后从最高分向最低分扫描遇到一个有效索引就按顺序发奖牌。public String[] findRelativeRanks(int[] score) { int n score.length; int max 0; for (int s : score) max Math.max(max, s); int[] bucket new int[max 1]; Arrays.fill(bucket, -1); for (int i 0; i n; i) bucket[score[i]] i; String[] ans new String[n]; int rank 1; for (int val max; val 0; val--) { if (bucket[val] ! -1) { if (rank 1) ans[bucket[val]] Gold Medal; else if (rank 2) ans[bucket[val]] Silver Medal; else if (rank 3) ans[bucket[val]] Bronze Medal; else ans[bucket[val]] String.valueOf(rank); rank; } } return ans; }这个方案的时间复杂度是O(n maxScore)空间复杂度O(maxScore)。当分数值域很大比如说分数区间有10^9量级这个做法会直接爆内存所以它不是通用方案了解即可能口算出原理就行。真正面试时回答排序 索引恢复的主流方案再提一句“如果分数值域可控还能用桶排序做到线性时间”基本就稳了。这里有个小细节bucket数组初始值不能是0因为下标0是一个合法索引所以用-1来做“没有这个分数”的标记否则你会把score[0]误判成“这个分数存在”从而在回填时把名次给错对象。像这种边界标记的初始化是桶排序最常见的翻车点。3.5 三种主流方案的复杂度对比方案时间复杂度空间复杂度代码复杂度适用场景暴力双重循环O(n^2)O(1)低数据量极小仅用于写伪代码排序 HashMapO(n log n)O(n)中最容易理解推荐初学索引数组排序O(n log n)O(n)中低面试首选回填方便桶排序O(n maxScore)O(maxScore)中分数值域可控且较小就这道题而言n最多也就一万左右排序 索引数组的做法是最均衡的。数据范围再大一点比如n到百万级O(n log n)仍然扛得住如果分数分布非常密集且值域不大桶排序才有机会感受到线性的快乐。但一般面试不会为了这题上桶排序。4. 上手过程实录我写这题时踩过的坑和排查方法4.1 第一次提交Comparator比较方向写反金牌发给了最低分我最初写索引数组排序时Comparator写成了(score[a] - score[b])也就是按升序排列。排序完成后idx[0]是最低分的原始下标。结果金牌顺理成章地发给了得分最低的人整个answer反过来了连着Silver和Bronze也全错。这个错的排查其实很快先打印idx数组看看排完序后的下标顺序是不是“从最高分到最低分”对应的顺序。只要idx数组顺序错了后面问题全错如果idx数组对但answer错那就是回填时奖牌映射逻辑的问题。遇到这类名次题建议第一步先检查排序结果第二步再检查回填映射别一上来就在if逻辑里找半天。4.2 第二个坑用int[]存索引Arrays.sort没法写自定义比较器我第一次写的时候下意识地声明了int[] idx new int[n]然后想用Arrays.sort(idx, (a, b) - ...)编译器直接报错。原因前面说过Arrays.sort只有对象数组版本才带Comparator参数int[]不满足条件。这个报错本身很友好编译器会提示找不到合适的方法但对不熟悉Java泛型的人来说很容易在“为什么int不行”上面卡住。解决就是换成Integer[]。这里也给出一个配套知识点如果你不想引入Integer[]装箱也可以用List Collections.sort来排。不过索引数组本身仍然需要包装List的元素只能是对象。所以Java里想把索引和数值绑定自定义排序绕不开Integer。写起来虽然有点啰嗦但这个包装类也带来了一个好处交换元素时比较的是Integer对象引用代码更直观。4.3 第三个坑HashMap解法中奖牌字符串和数字名次的优先级写混用HashMap解法时如果把前三名逻辑写在put之后很容易把前三名也当成普通名次覆盖掉。比如rankMap.put(sorted[i], String.valueOf(n - i)); if (i n - 1) rankMap.put(sorted[i], Gold Medal);这种顺序也可能正确因为后面put会覆盖前面put但你得确保排序的遍历顺序是从高到低否则一混淆整个映射就乱了。更稳妥的写法是先处理前三名再在else里处理普通名次。逻辑越简单出错的概率越低。代码层面建议这样组织for (int i n - 1; i 0; i--) { if (i n - 1) { rankMap.put(sorted[i], Gold Medal); } else if (i n - 2) { rankMap.put(sorted[i], Silver Medal); } else if (i n - 3) { rankMap.put(sorted[i], Bronze Medal); } else { rankMap.put(sorted[i], String.valueOf(n - i)); } }4.4 边界情况n 1、n 2时代码能不能扛住n 1时循环只会执行一次i等于0走的是Gold Medal分支返回[Gold Medal]没问题。n 2时循环两次i分别等于1和0注意在排序 HashMap的写法里数组sorted是升序的第0个元素是最小分第1个元素是最大分。遍历从大到小先给最大分发Gold再给最小分发Silver输出answer下标时正好对应。我用这个思路测过一个只有两名运动员的用例返回[Silver Medal, Gold Medal]是正确顺序。这个边界别跳过很多排名题因为没有考虑n 3而出现数组越界或空指针。这里的窍门是始终用“索引回填”而不是“顺序填充”天然不会受n大小影响。4.5 常见问题速查表现象可能原因解决思路名次整体相反Comparator比较方向写反检查降序还是升序建议打印idx数组确认编译报错找不到sort方法用了int[]却没有用Integer[]换成Integer[]或用List前三名全变成普通数字奖牌分支被else覆盖先处理奖牌再处理普通名次HashMap取值出现null排序数组和原数据不一致确认排序的是得分不是下标桶排序结果错乱bucket初始值用了0用-1标记“无此分数”代码通过但可读性差if逻辑嵌套太多抽一个getRankName方法或使用三目5. 把这题放进真实项目竞赛排名模块远不止“排序”这么简单5.1 一个实际场景给一批成绩回填名次我参与过一个小型的线上运动会成绩汇总模块需求是这样的系统里有几百名选手每名选手都有成绩前端页面上需要在每个选手的名字旁边显示名次前三名显示奖牌图标。后端最直接的实现就是把选手列表按成绩降序排列然后从第一名开始逐条给选手记录写入名次。但这里有个问题数据库里选手记录是乱序的如果只按排序后的List更新你要么把名次返回给前端让前端按索引显示要么在更新时通过选手id回写数据库。后者就对应到LeetCode 506的“原始下标恢复”问题——排序后你还是要找到“某个选手原本记录在哪个位置”然后精确回填。实际做的时候排序用的不是“成绩值”而是“选手id 成绩”的二元组。对id数组排序比较器参考成绩排序后id数组的排列顺序就是名次顺序这跟这题里的索引数组排序完全同构。5.2 真实名次系统要考虑并列排名LeetCode 506明确说了所有得分互不相同但真实项目里并列太常见了。两个人同分谁排前面常见规则有两种。第一种并列名次跳过编号比如两个人并列第二名名次序列是1、2、2、4第三名空缺。第二种并列后仍连续编号名次序列是1、2、2、3。这两种规则对应的算法差别很大。第一种需要你先把同分的人归到一组每组统一给一个名次然后下一组的名次要加上这一组的人数。第二种则相对简单你可以先排序然后遍历时如果成绩相同就沿用前一个名次否则更新为序号。我在项目里遇到过产品经理临时改规则的情况所以这类排名逻辑抽出独立方法不要和主流程写在一起。LeetCode 506虽然不考虑并列但它训练的这个“排序 回填”思维放到真实姓名排名里同样适用。5.3 如果人数特别多TopK和外部排序假设你有几千万选手成绩不可能一次性全都排序放进内存。这时真正的需求往往也不是“给所有人排名”而是“我只想知道前100名”。这类TopK问题主流做法是维护一个容量为k的最小堆遍历每一个成绩如果堆没满就插入堆满了如果当前成绩比堆顶大就替换堆顶并调整堆。这样遍历完所有数据后堆里留下来的就是最大的k个成绩堆顶是这k个里的最小值。这个思路和相对名次有关联但又不完全一样。相对名次要求全量排名TopK只要求局部。做项目时先跟业务确认清楚“你要全排名还是只看头部”这两种方案的时间和空间成本完全是两个量级。全排名用O(n log n)排序TopK用O(n log k)堆当n是一千万时这个差距会非常明显。5.4 从“相对名次”看排序题的通用骨架这题对刷题者的最大价值是提炼出了一个通用骨架数据源是一组带“唯一标识”的元素。需要按某个指标做全量或局部排序。排序结果必须关联回原始的唯一标识。只要看到题目里出现“返回每个位置的排名”“按原始顺序输出名次”“判断谁比谁高”这类描述优先考虑“索引数组排序”这个万能解法。它不光能解相对名次还能解一大批类似题目比如“按分数给学生排名次并统计每个名次人数”“按照某字段排序后输出原字段对应的新值”等。我举一个变式如果题目改成“给定一组得分输出每个得分在所有得分中的百分位排名”你会怎么做第一反应可能是排序后二分查找。但如果得分有重复值你得先确定排名口径。这又回到了并列排名讨论里的语义问题。所以506存在的意义不只是背一个解法而是逼你想清楚“排序的价值到底是什么”。6. 我个人的体会这道简单题不必五分钟刷完值得拆开多写几遍这道题我刷完第一遍之后又隔了一周重新写了一遍。第二次写的时候我有意不再用HashMap而是用索引数组排序然后明显感觉到自己对“排序对象可以不是数据本身而是索引”这件事的理解变得更具体了。后来我在某个小型计分项目里恰好需要按得分给记录排序并回填名次。当时的场景比LeetCode 506更绕每条记录除了得分还有多个展示字段不能简单把排序结果当成输出顺序必须按原始记录号精确回填。我第一时间就想到了索引数组排序几分钟就把功能写完了测试也没踩坑。那一刻确实觉得刷题这事不是白刷的。最后分享一个小技巧凡是这种“给了原始数组要求按原始位置输出某种排名结果”的题目先问自己一个问题——“排序过程中每个元素的原始位置信息还在不在”如果不在优先想到索引数组排序如果还在那就是直接排序或者用哈希表缓存排名。带着这个判断框架去做题比单纯记代码要管用得多。 
长河君 · 2026/10/22 11:06:01 · 阅读 1.2k 排序后索引恢复：LeetCode 506相对名次题解
1. 从“相对名次”这道LeetCode简单题看清排序题的隐藏考点2021年12月2日的每日一题碰上的是506这道“相对名次”。题面很直白给你一个整数数组scorescore[i]是第i名运动员的得分所有得分互不相同要求返回一个字符串数组answeranswer[i]表示第i名运动员的名次。第一名是“Gold Medal”第二名是“Silver Medal”第三名是“Bronze Medal”从第四名开始直接返回数字字符串比如“4”“5”“6”。这道题在LeetCode上被标为简单题。说实话第一次看到题目描述我脑子里冒出来的第一个想法是这不就是把分数排个序然后按顺序发奖牌嘛。但真正动手写的时候才发现这个“简单题”里藏着好几个容易翻车的细节尤其是“排序后会丢失原始下标”这个问题。很多刷题新手会在这里卡住要么排序后不知道该怎么把名次填回原数组要么为了找回下标写出一堆难看的代码。这题适合谁我觉得三类人都值得做一遍刚接触算法题、正在建立排序解题框架的人准备面试、想复习“排序 索引恢复”这个经典套路的人以及在职场上偶尔要处理“按成绩/得分排名并回填展示需求”的开发同学。题目本身不难但背后延伸出去的思维模型不少下面我按自己的复盘过程来拆。2. 核心思路拆解排序后怎么找回原始下标才是真正的考点2.1 先读懂题目的输入输出关系假设score [10, 3, 8, 9, 4]五个运动员的下标分别是0、1、2、3、4。得分最高的是下标0的10分所以answer[0] “Gold Medal”第二高的是下标3的9分answer[3] “Silver Medal”第三高的是下标2的8分answer[2] “Bronze Medal”剩下下标4的4分排第四answer[4] “4”下标1的3分排第五answer[1] “5”。最后返回[Gold Medal, 5, Bronze Medal, Silver Medal, 4]。这里最关键的点在于名次是按得分从高到低排列的但输出必须回到原始数组的每个下标的对应位置。如果直接对score做排序比如排成[10, 9, 8, 4, 3]你得到了一个降序列表却不知道10分是原来哪个下标的9分是原来哪个下标的。所有后续的“回填”都会变得很别扭。所以解题的命门是排序的“参照物”要带着原始下标一起走。2.2 思路一先排序再用HashMap记录每个分数的名次最直观的方案是复制一份得分数组对复制体做降序排序。排序后遍历这个有序数组用一个HashMap把“得分 - 名次”存下来。最后遍历原始score数组去map里查每个得分对应什么名次填入answer。这个思路很符合第一直觉先建立“分数到名次”的映射再原路走一遍。优点是容易理解代码写起来也顺。缺点是多了个哈希表的开销而且在Java里HashMap会涉及Integer的自动装箱和hash计算虽然这题数据量不大性能上没压力但实现起来有一种“绕了一圈”的感觉。代码大概是下面这个样子public String[] findRelativeRanks(int[] score) { int n score.length; int[] sorted score.clone(); Arrays.sort(sorted); MapInteger, String rankMap new HashMap(); for (int i n - 1; i 0; i--) { if (i n - 1) { rankMap.put(sorted[i], Gold Medal); } else if (i n - 2) { rankMap.put(sorted[i], Silver Medal); } else if (i n - 3) { rankMap.put(sorted[i], Bronze Medal); } else { rankMap.put(sorted[i], String.valueOf(n - i)); } } String[] ans new String[n]; for (int i 0; i n; i) { ans[i] rankMap.get(score[i]); } return ans; }因为Java默认的Arrays.sort是升序排序所以从后往前遍历第一个取到的就是最高分。n - i这个公式正好表示名次i从n-1开始n - (n - 1) 1in-2时n - (n-2) 2以此类推正好对应第1名、第2名。这里有个小坑如果直接用for循环里的i来算名次很多人写成了n - i却忘了加1或者忘了处理前三名调试时反复在边界上撞车。后面我会专门讲这些问题。2.3 思路二对索引数组排序从根上避免丢下标推荐既然问题的核心是“排序后不知道原始下标”那能不能让“原始下标”本身就是排序的对象可以。构造一个Integer[] index数组里面装0、1、2、…、n - 1用自定义比较器按照score[index[i]]的大小对index数组排序。排序后index[0]就是得分最高的原始下标index[1]是第二高的原始下标。直接遍历index数组依次填入Gold Medal、Silver Medal、Bronze Medal和数字名次。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]; for (int i 0; i n; i) { if (i 0) { ans[idx[i]] Gold Medal; } else if (i 1) { ans[idx[i]] Silver Medal; } else if (i 2) { ans[idx[i]] Bronze Medal; } else { ans[idx[i]] String.valueOf(i 1); } } return ans; }这段代码的精髓在于排序的对象不是分数本身而是“下标清单”。分数只是比较时的参照物。排序完成之后idx数组自带了一个信息排在第i位的是原始下标为idx[i]的运动员。这样回填答案时直接ans[idx[i]] 对应名次一步到位不需要哈希表也不需要clone数组。第一次看到这个写法的人可能会觉得别扭为什么要用一个Integer[]而不是int[]因为在Java里Arrays.sort只有针对对象数组的重载版本才支持自定义Comparatorint[]只能按自然顺序排没法降序排。想自定义比较器就得用Integer[]。2.4 为什么不能直接对原数组排序这题最容易出的错误就是“先排序原数组再直接从前往后发奖牌”。比如Arrays.sort(score);排完之后数组里确实是从小到大或从大到小的顺序但你丢失了“每个分数原本属于哪个下标”的信息后面想构建answer数组时你根本不知道answer[某个原始下标]该填什么。有人可能会说那我再找一下每个分数在排序后的位置这其实就是退回了O(n^2)遍历不仅笨而且很容易处理不好重复值本题说得分互不相同还好万一有重复就彻底乱了。所以无论采用哪种解法“带着原始身份去排序”或“排序后再建立映射”是绕不开的关键点。3. 完整实现详解代码逐步拆开看每个细节都讲透3.1 为什么用“分数差”作为比较器有风险在上面的索引数组排序里比较器写的是(score[b] - score[a])这在高性能要求下很常见也很简洁。但很多教科书和面试官会追问一个问题如果score[b] - score[a]整型溢出怎么办这题里score[i]的范围是0到10^6两个分数的差值最多也就是10^6远小于int上限21亿所以不会溢出。但万一题目改一下分数范围变成int的正负极值两个大数相减就可能溢出导致错乱。稳妥的写法是用Integer.compare(score[b], score[a])它的内部实现是大于、小于、等于三个分支比较不会做减法没有溢出风险。我个人建议刷题时如果数据范围明确安全用减法写法简洁没问题但写进简历项目或面试手写时优先用Integer.compare显得更严谨。还可以写成Arrays.sort(idx, (a, b) - Integer.compare(score[b], score[a]));代码可读性更好也不至于被面试官抓到“这里可能溢出”的小尾巴。3.2 主循环里前三名的处理顺序有没有更优雅的写法主循环里我写了if、else if、else if、else四段把前三名和其他名次分开处理。有人觉得啰嗦想用一个String数组存奖牌名然后用i 3去判断String[] medals {Gold Medal, Silver Medal, Bronze Medal}; for (int i 0; i n; i) { ans[idx[i]] i 3 ? medals[i] : String.valueOf(i 1); }这种写法确实更简洁但要注意medals数组的下标正好是0、1、2分别对应第一名、第二名、第三名刚好和i对应。如果选手人数少于3人例如n 1循环只执行一次i 0取medals[0]没问题。n 2时取Gold Medal和Silver Medal也没问题。所以三目运算的写法非常安全。不过很多公司笔试环境里代码的“显式可读性”比“短”更重要。四段if写法一眼就能看清楚边界逻辑三目写法虽然短但容易让人在“i 3”这个条件上顿一下。我个人在刷题时用三目写法比较多在写业务代码时用if分支比较多看场景取舍。3.3 数字名次为什么要用String.valueOf从第四名开始名次要转成字符串。很多人直接写ans[idx[i]] (i 1) 这在Java里也能工作因为字符串拼接会自动把整数转成字符串。但要注意如果这个代码段在循环里被频繁执行拼接会创建额外的StringBuilder对象虽然现代JIT会做优化但写代码时养成用String.valueOf的习惯更干净。其实本题的n不超过一万两种写法性能没有任何肉眼可见的差别。审美上的选择而已。但用String.valueOf至少不会让读者疑惑“是不是在拼接字符串”语义更明确。3.4 桶排序做法知道即可别当主方案因为score[i]范围固定是0到10^6还可以用“计数 倒序扫描”的桶思路来做。开一个长度为maxScore 1的数组bucketbucket[score[i]] i记录每个分数对应的原始下标。然后从最高分向最低分扫描遇到一个有效索引就按顺序发奖牌。public String[] findRelativeRanks(int[] score) { int n score.length; int max 0; for (int s : score) max Math.max(max, s); int[] bucket new int[max 1]; Arrays.fill(bucket, -1); for (int i 0; i n; i) bucket[score[i]] i; String[] ans new String[n]; int rank 1; for (int val max; val 0; val--) { if (bucket[val] ! -1) { if (rank 1) ans[bucket[val]] Gold Medal; else if (rank 2) ans[bucket[val]] Silver Medal; else if (rank 3) ans[bucket[val]] Bronze Medal; else ans[bucket[val]] String.valueOf(rank); rank; } } return ans; }这个方案的时间复杂度是O(n maxScore)空间复杂度O(maxScore)。当分数值域很大比如说分数区间有10^9量级这个做法会直接爆内存所以它不是通用方案了解即可能口算出原理就行。真正面试时回答排序 索引恢复的主流方案再提一句“如果分数值域可控还能用桶排序做到线性时间”基本就稳了。这里有个小细节bucket数组初始值不能是0因为下标0是一个合法索引所以用-1来做“没有这个分数”的标记否则你会把score[0]误判成“这个分数存在”从而在回填时把名次给错对象。像这种边界标记的初始化是桶排序最常见的翻车点。3.5 三种主流方案的复杂度对比方案时间复杂度空间复杂度代码复杂度适用场景暴力双重循环O(n^2)O(1)低数据量极小仅用于写伪代码排序 HashMapO(n log n)O(n)中最容易理解推荐初学索引数组排序O(n log n)O(n)中低面试首选回填方便桶排序O(n maxScore)O(maxScore)中分数值域可控且较小就这道题而言n最多也就一万左右排序 索引数组的做法是最均衡的。数据范围再大一点比如n到百万级O(n log n)仍然扛得住如果分数分布非常密集且值域不大桶排序才有机会感受到线性的快乐。但一般面试不会为了这题上桶排序。4. 上手过程实录我写这题时踩过的坑和排查方法4.1 第一次提交Comparator比较方向写反金牌发给了最低分我最初写索引数组排序时Comparator写成了(score[a] - score[b])也就是按升序排列。排序完成后idx[0]是最低分的原始下标。结果金牌顺理成章地发给了得分最低的人整个answer反过来了连着Silver和Bronze也全错。这个错的排查其实很快先打印idx数组看看排完序后的下标顺序是不是“从最高分到最低分”对应的顺序。只要idx数组顺序错了后面问题全错如果idx数组对但answer错那就是回填时奖牌映射逻辑的问题。遇到这类名次题建议第一步先检查排序结果第二步再检查回填映射别一上来就在if逻辑里找半天。4.2 第二个坑用int[]存索引Arrays.sort没法写自定义比较器我第一次写的时候下意识地声明了int[] idx new int[n]然后想用Arrays.sort(idx, (a, b) - ...)编译器直接报错。原因前面说过Arrays.sort只有对象数组版本才带Comparator参数int[]不满足条件。这个报错本身很友好编译器会提示找不到合适的方法但对不熟悉Java泛型的人来说很容易在“为什么int不行”上面卡住。解决就是换成Integer[]。这里也给出一个配套知识点如果你不想引入Integer[]装箱也可以用List Collections.sort来排。不过索引数组本身仍然需要包装List的元素只能是对象。所以Java里想把索引和数值绑定自定义排序绕不开Integer。写起来虽然有点啰嗦但这个包装类也带来了一个好处交换元素时比较的是Integer对象引用代码更直观。4.3 第三个坑HashMap解法中奖牌字符串和数字名次的优先级写混用HashMap解法时如果把前三名逻辑写在put之后很容易把前三名也当成普通名次覆盖掉。比如rankMap.put(sorted[i], String.valueOf(n - i)); if (i n - 1) rankMap.put(sorted[i], Gold Medal);这种顺序也可能正确因为后面put会覆盖前面put但你得确保排序的遍历顺序是从高到低否则一混淆整个映射就乱了。更稳妥的写法是先处理前三名再在else里处理普通名次。逻辑越简单出错的概率越低。代码层面建议这样组织for (int i n - 1; i 0; i--) { if (i n - 1) { rankMap.put(sorted[i], Gold Medal); } else if (i n - 2) { rankMap.put(sorted[i], Silver Medal); } else if (i n - 3) { rankMap.put(sorted[i], Bronze Medal); } else { rankMap.put(sorted[i], String.valueOf(n - i)); } }4.4 边界情况n 1、n 2时代码能不能扛住n 1时循环只会执行一次i等于0走的是Gold Medal分支返回[Gold Medal]没问题。n 2时循环两次i分别等于1和0注意在排序 HashMap的写法里数组sorted是升序的第0个元素是最小分第1个元素是最大分。遍历从大到小先给最大分发Gold再给最小分发Silver输出answer下标时正好对应。我用这个思路测过一个只有两名运动员的用例返回[Silver Medal, Gold Medal]是正确顺序。这个边界别跳过很多排名题因为没有考虑n 3而出现数组越界或空指针。这里的窍门是始终用“索引回填”而不是“顺序填充”天然不会受n大小影响。4.5 常见问题速查表现象可能原因解决思路名次整体相反Comparator比较方向写反检查降序还是升序建议打印idx数组确认编译报错找不到sort方法用了int[]却没有用Integer[]换成Integer[]或用List前三名全变成普通数字奖牌分支被else覆盖先处理奖牌再处理普通名次HashMap取值出现null排序数组和原数据不一致确认排序的是得分不是下标桶排序结果错乱bucket初始值用了0用-1标记“无此分数”代码通过但可读性差if逻辑嵌套太多抽一个getRankName方法或使用三目5. 把这题放进真实项目竞赛排名模块远不止“排序”这么简单5.1 一个实际场景给一批成绩回填名次我参与过一个小型的线上运动会成绩汇总模块需求是这样的系统里有几百名选手每名选手都有成绩前端页面上需要在每个选手的名字旁边显示名次前三名显示奖牌图标。后端最直接的实现就是把选手列表按成绩降序排列然后从第一名开始逐条给选手记录写入名次。但这里有个问题数据库里选手记录是乱序的如果只按排序后的List更新你要么把名次返回给前端让前端按索引显示要么在更新时通过选手id回写数据库。后者就对应到LeetCode 506的“原始下标恢复”问题——排序后你还是要找到“某个选手原本记录在哪个位置”然后精确回填。实际做的时候排序用的不是“成绩值”而是“选手id 成绩”的二元组。对id数组排序比较器参考成绩排序后id数组的排列顺序就是名次顺序这跟这题里的索引数组排序完全同构。5.2 真实名次系统要考虑并列排名LeetCode 506明确说了所有得分互不相同但真实项目里并列太常见了。两个人同分谁排前面常见规则有两种。第一种并列名次跳过编号比如两个人并列第二名名次序列是1、2、2、4第三名空缺。第二种并列后仍连续编号名次序列是1、2、2、3。这两种规则对应的算法差别很大。第一种需要你先把同分的人归到一组每组统一给一个名次然后下一组的名次要加上这一组的人数。第二种则相对简单你可以先排序然后遍历时如果成绩相同就沿用前一个名次否则更新为序号。我在项目里遇到过产品经理临时改规则的情况所以这类排名逻辑抽出独立方法不要和主流程写在一起。LeetCode 506虽然不考虑并列但它训练的这个“排序 回填”思维放到真实姓名排名里同样适用。5.3 如果人数特别多TopK和外部排序假设你有几千万选手成绩不可能一次性全都排序放进内存。这时真正的需求往往也不是“给所有人排名”而是“我只想知道前100名”。这类TopK问题主流做法是维护一个容量为k的最小堆遍历每一个成绩如果堆没满就插入堆满了如果当前成绩比堆顶大就替换堆顶并调整堆。这样遍历完所有数据后堆里留下来的就是最大的k个成绩堆顶是这k个里的最小值。这个思路和相对名次有关联但又不完全一样。相对名次要求全量排名TopK只要求局部。做项目时先跟业务确认清楚“你要全排名还是只看头部”这两种方案的时间和空间成本完全是两个量级。全排名用O(n log n)排序TopK用O(n log k)堆当n是一千万时这个差距会非常明显。5.4 从“相对名次”看排序题的通用骨架这题对刷题者的最大价值是提炼出了一个通用骨架数据源是一组带“唯一标识”的元素。需要按某个指标做全量或局部排序。排序结果必须关联回原始的唯一标识。只要看到题目里出现“返回每个位置的排名”“按原始顺序输出名次”“判断谁比谁高”这类描述优先考虑“索引数组排序”这个万能解法。它不光能解相对名次还能解一大批类似题目比如“按分数给学生排名次并统计每个名次人数”“按照某字段排序后输出原字段对应的新值”等。我举一个变式如果题目改成“给定一组得分输出每个得分在所有得分中的百分位排名”你会怎么做第一反应可能是排序后二分查找。但如果得分有重复值你得先确定排名口径。这又回到了并列排名讨论里的语义问题。所以506存在的意义不只是背一个解法而是逼你想清楚“排序的价值到底是什么”。6. 我个人的体会这道简单题不必五分钟刷完值得拆开多写几遍这道题我刷完第一遍之后又隔了一周重新写了一遍。第二次写的时候我有意不再用HashMap而是用索引数组排序然后明显感觉到自己对“排序对象可以不是数据本身而是索引”这件事的理解变得更具体了。后来我在某个小型计分项目里恰好需要按得分给记录排序并回填名次。当时的场景比LeetCode 506更绕每条记录除了得分还有多个展示字段不能简单把排序结果当成输出顺序必须按原始记录号精确回填。我第一时间就想到了索引数组排序几分钟就把功能写完了测试也没踩坑。那一刻确实觉得刷题这事不是白刷的。最后分享一个小技巧凡是这种“给了原始数组要求按原始位置输出某种排名结果”的题目先问自己一个问题——“排序过程中每个元素的原始位置信息还在不在”如果不在优先想到索引数组排序如果还在那就是直接排序或者用哈希表缓存排名。带着这个判断框架去做题比单纯记代码要管用得多。