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

昨天晚上十一点多，在公司楼下蹲着喝奶茶刷题，隔壁组那个小李突然喊我，“哥，我这个相对名次你给我说人话版的呗，题解看困了”。我一看题目，其实还挺生活化的。

大概意思就是这样：

• 给你一堆同学的得分 int[] score，每个人只考一次
• 分数互不相同（这个条件很关键）
• 你要按分数从高到低排出名次
• 返回一个 String[]，第 i 个位置就是第 i 个同学的“名次字符串”

前 3 名要写成：

• 第一名："Gold Medal"
• 第二名："Silver Medal"
• 第三名："Bronze Medal"

从第 4 名开始，就直接用名次数字："4"、"5"……这样。

比如：

score = [10, 3, 8, 9, 4]

分数从大到小排序：10(0号), 9(3号), 8(2号), 4(4号), 3(1号)

最后返回：
["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

注意一点：返回数组要按原下标排，不能排完序就直接返回，否则人都对不上号了。

我当时跟小李说，这题就两步：

1. 想办法把“分数排序后的名次”算出来
2. 再把这个名次“放回”到原来的同学位置上

实现上，比较顺手的写法就是——分数 + 原始下标 打包在一起排序。

大概脑补成一张表：

把这张表按分数从大到小排，排完以后，从上往下走一遍，第 1 行是第 1 名，第 2 行是第 2 名…… 但真正写结果的时候，要用“原始下标”去填结果数组。

直接上一个完整方法，能过题那种：

import java.util.Arrays;

publicclassRelativeRanks{

public String[] findRelativeRanks(int[] score) {
int n = score.length;
        String[] ans = new String[n];
if (n == 0) {
return ans;
        }

// 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]);

for (int rank = 0; rank < n; rank++) {
int index = pairs[rank][1]; // 原数组的下标
if (rank == 0) {
                ans[index] = "Gold Medal";
            } elseif (rank == 1) {
                ans[index] = "Silver Medal";
            } elseif (rank == 2) {
                ans[index] = "Bronze Medal";
            } else {
                ans[index] = String.valueOf(rank + 1);
            }
        }

return ans;
    }
}

你在 main 里随便测下：

publicstaticvoidmain(String[] args){
    RelativeRanks r = new RelativeRanks();
int[] score = {10, 3, 8, 9, 4};
    System.out.println(Arrays.toString(r.findRelativeRanks(score)));
}

打印出来就是：[Gold Medal, 5, Bronze Medal, Silver Medal, 4]，OK 的。

别看题简单，面试的时候一般还会顺手追问两句，你心里有数就行：

• 排序这一步是瓶颈：Arrays.sort，时间复杂度 O(n log n)
• 构造 pairs 和最后那一圈循环：O(n)
• 额外空间：pairs 这个二维数组，占了 O(n)

整体就是：**时间 O(n log n)，空间 O(n)**，很正常的水平。

为啥要存“原始下标”，不能只排分数？

这个小李当时就问我：“我直接把 score 排序不行吗？”

问题就出在——你排完 score 之后，丢了“这分是谁的”信息。

比如：

原数组： score = [10, 3, 8]
排序后： [3, 8, 10]

你知道 10 是第一名，但你不知道 10 原来在 0 号位置，除非你再倒推，很折腾。 所以打包成 (score, index)，一排完序，既有顺序，又能找到人，这一点实战里特别常用，很多“排序 + 保留原位置”的题都是这套路。 （顺嘴说一句，我之前看数据库压测对比 MySQL 和 Postgres 的文章，里面也疯狂在各种维度上“打包指标排序”，套路是一样的）

还有没有别的写法？

有的，不过都是一个意思。

比如用大顶堆（优先队列）：

1. 把 (score[i], i) 全丢进优先队列，比较规则是分数大的优先
2. 每次 poll() 出来一个，就是当前名次最高的，rank 从 1 往下加
3. 和刚才一样，前 3 名特殊字符串，后面转数字

伪代码感受一下就行：

PriorityQueue<int[]> pq = new PriorityQueue<>(
        (a, b) -> b[0] - a[0]
);
// 入堆、出堆逻辑跟上面排序那套几乎一样

复杂度也是 O(n log n)，只是把“排序”换成了“堆”。一般刷题我更偏向前面那个排序 + 数组的方式，更短更直观。

差不多就这样，我奶茶都喝完了，小李那会儿也把这题 AC 掉了。你要是还有别的算法题想用这种“人话+Java源码”的方式说一遍，丢过来就行，我慢慢聊。