相对名次
难度:
标签:
题目描述
给你一个长度为 n
的整数数组 score
,其中 score[i]
是第 i
位运动员在比赛中的得分。所有得分都 互不相同 。
运动员将根据得分 决定名次 ,其中名次第 1
的运动员得分最高,名次第 2
的运动员得分第 2
高,依此类推。运动员的名次决定了他们的获奖情况:
- 名次第
1
的运动员获金牌"Gold Medal"
。 - 名次第
2
的运动员获银牌"Silver Medal"
。 - 名次第
3
的运动员获铜牌"Bronze Medal"
。 - 从名次第
4
到第n
的运动员,只能获得他们的名次编号(即,名次第x
的运动员获得编号"x"
)。
使用长度为 n
的数组 answer
返回获奖,其中 answer[i]
是第 i
位运动员的获奖情况。
示例 1:
输入:score = [5,4,3,2,1] 输出:["Gold Medal","Silver Medal","Bronze Medal","4","5"] 解释:名次为 [1st, 2nd, 3rd, 4th, 5th] 。
示例 2:
输入:score = [10,3,8,9,4] 输出:["Gold Medal","5","Bronze Medal","Silver Medal","4"] 解释:名次为 [1st, 5th, 3rd, 2nd, 4th] 。
提示:
n == score.length
1 <= n <= 104
0 <= score[i] <= 106
score
中的所有值 互不相同
代码结果
运行时间: 31 ms, 内存: 17.3 MB
// Java Stream solution for the problem
// The idea is to use Streams to sort the scores and assign medals or ranks based on the sorted order
import java.util.*;
import java.util.stream.*;
public class SolutionStream {
public String[] findRelativeRanks(int[] score) {
int n = score.length;
// Create a map of score to index
Map<Integer, Integer> scoreToIndex = IntStream.range(0, n)
.boxed()
.collect(Collectors.toMap(i -> score[i], i -> i));
// Sort scores in descending order
List<Integer> sortedScores = Arrays.stream(score)
.boxed()
.sorted(Comparator.reverseOrder())
.collect(Collectors.toList());
// Prepare the result array
String[] result = new String[n];
for (int i = 0; i < sortedScores.size(); i++) {
int index = scoreToIndex.get(sortedScores.get(i));
if (i == 0) {
result[index] = "Gold Medal";
} else if (i == 1) {
result[index] = "Silver Medal";
} else if (i == 2) {
result[index] = "Bronze Medal";
} else {
result[index] = String.valueOf(i + 1);
}
}
return result;
}
}
解释
方法:
该题解首先对输入数组score进行排序,并反转,使得排序后的数组ss按分数从高到低排列。随后,使用列表推导式和enumerate创建一个字典dic,该字典将每个分数映射到其在排序数组中的索引(即名次),由于名次是从1开始的,所以对每个索引加1。然后,对原始score数组中的每个分数查找其名次,根据名次判断赋予相应的奖牌:前三名分别获得'Gold Medal'、'Silver Medal'、'Bronze Medal',其余按名次数字赋值。最后返回结果列表res,该列表包含每个运动员的获奖情况。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在构建名次字典时选择使用列表推导式和enumerate,而不是直接迭代排序后的数组?
▷🦆
在处理特殊的奖牌(金、银、铜)时,如果未来需要增加更多特殊奖牌,如何优化代码以便轻松添加或修改奖牌的逻辑?
▷🦆
题解中将排序后的数组ss和原始score数组分别遍历了一次,是否存在可能通过单次遍历实现相同的结果构建?
▷🦆
题解中未处理score数组为空的情况,应如何修改代码以确保能处理空数组输入?
▷