大厂员工自爆:去年在大厂,年薪95万,女朋友父母爱答不理,今年上岸国家电网,人不到,叔叔阿姨吃饭都不让动筷子

我先说个生活里的事啊。

前两天我们组搞团建，去公司楼下操场跑步比赛，完事儿大家在那儿吵吵： “我是第二吧？” “你肯定排我后面，我比你先冲线的！”

我在旁边看着就乐，这不就是一道典型的算法题嘛：一堆人的成绩，怎么给每个人标上名次，还得能区分出“金银铜牌”。

算法题名字就叫：相对名次（Relative Ranks）。

给你一个 int[] score，里面是每个选手的得分，分数越大名次越靠前。 要求返回一个 String[]，下标跟原数组对应：

• 分数最高的那个位置放 "Gold Medal"
• 第二名 "Silver Medal"
• 第三名 "Bronze Medal"
• 后面的就放名次数字，比如 "4", "5" 这样

注意一点：返回结果的顺序，是“原来的顺序”，不是排完序的顺序。

你可以先想象一下操场场景：

1. 比赛结束，大家都站成一排（这就是原始数组，按下标站）
2. 裁判把每个人拉出来，按成绩排一个名次榜（这就是我们自己排的“排序数组”）
3. 排完以后，再跑回去跟每个人说：“喂，你原来在第 i 个位置，你是第 k 名”

用程序做就是三步：

1. 把每个人的信息打包成：(分数, 原下标)
2. 按“分数”从大到小排个序
3. 按排好序的结果，去给对应的“原下标”填字符串名次

这样既能确定名次，又不会丢掉原来是谁是谁。

直接上代码，你们可以拷到本地跑一下：

import java.util.Arrays;publicclassRelativeRanks{public String[] findRelativeRanks(int[] score) {int n = score.length;// pairs[i][0] = 分数, pairs[i][1] = 原来的下标int[][] pairs = newint[n][2];for (int i = 0; i < n; i++) {            pairs[i][0] = score[i];            pairs[i][1] = i;        }// 按分数从大到小排序        Arrays.sort(pairs, (a, b) -> b[0] - a[0]);        String[] ans = new String[n];for (int rank = 0; rank < n; rank++) {int idx = pairs[rank][1]; // 原来的下标if (rank == 0) {                ans[idx] = "Gold Medal";            } elseif (rank == 1) {                ans[idx] = "Silver Medal";            } elseif (rank == 2) {                ans[idx] = "Bronze Medal";            } else {                ans[idx] = String.valueOf(rank + 1);            }        }return ans;    }// 简单测一下publicstaticvoidmain(String[] args){        RelativeRanks rr = new RelativeRanks();int[] score = {10, 3, 8, 9, 4};        String[] res = rr.findRelativeRanks(score);for (String s : res) {            System.out.println(s);        }// 输出应该是：// Gold Medal// 5// Bronze Medal// Silver Medal// 4    }}

你可以注意两个点：

1. 排序用的是 Arrays.sort，带一个自定义比较器 (a, b) -> b[0] - a[0]，表示按分数从高到低排
2. 赋值的时候用的是 pairs[rank][1] 这个“原下标”，保证结果数组跟最初传进来的顺序是一一对应的

简单算一下复杂度哈：

• 构造那个 pairs 数组：遍历一遍，O(n)
• 排序：O(n log n)
• 再遍历一遍发奖牌：O(n)

整体就是 O(n log n)，对于面试题、OJ题都足够用了，逻辑上也比较直观，不是那种“看不懂但好像很快”的写法。

内存方面，我们额外开了一个 int[n][2] 和一个 String[n]，空间复杂度 O(n)，也没啥问题。

有些同学一上来就写成这样：

Arrays.sort(score); // 把原数组直接排了

这样会有两个坑：

1. 原数组被你改顺序了，后面你就不知道“谁是谁”了
2. 题目要求结果要按照“原下标顺序”返回，你改了顺序就很难往回对

所以一定要记住：排序用的是“分数 + 原下标”的副本，原数组不要动它。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html