给你一个长度为 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.length1 <= n <= 1040 <= score[i] <= 106score 中的所有值 互不相同
方法一：排序
题目要求找到每个运动员的相对名次，并同时给前三名标记为 “Gold Medal”, “Silver Medal”, “Bronze Medal”，其余的运动员则标记为其相对名次。
将所有的运动员按照成绩的高低进行排序，然后将按照名次进行标记即可。
代码
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public String[] findRelativeRanks(int[] score) {
int n = score.length;
String[] desc = {"Gold Medal", "Silver Medal", "Bronze Medal"};
int[][] arr = new int[n][2];
for (int i = 0; i < n; ++i) {
arr[i][0] = score[i];
arr[i][1] = i;
}
Arrays.sort(arr, (a, b) -> b[0] - a[0]);
String[] ans = new String[n];
for (int i = 0; i < n; ++i) {
if (i >= 3) {
ans[arr[i][1]] = Integer.toString(i + 1);
} else {
ans[arr[i][1]] = desc[i];
}
}
return ans;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<string> findRelativeRanks(vector<int>& score) {
int n = score.size();
string desc[3] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
vector<pair<int, int>> arr;
for (int i = 0; i < n; ++i) {
arr.emplace_back(make_pair(-score[i], i));
}
sort(arr.begin(), arr.end());
vector<string> ans(n);
for (int i = 0; i < n; ++i) {
if (i >= 3) {
ans[arr[i].second] = to_string(i + 1);
} else {
ans[arr[i].second] = desc[i];
}
}
return ans;
}
};
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public string[] FindRelativeRanks(int[] score) {
int n = score.Length;
string[] desc = {"Gold Medal", "Silver Medal", "Bronze Medal"};
int[][] arr = new int[n][];
for (int i = 0; i < n; ++i) {
arr[i] = new int[2];
arr[i][0] = score[i];
arr[i][1] = i;
}
Array.Sort(arr, (a, b) => b[0] - a[0]);
string[] ans = new string[n];
for (int i = 0; i < n; ++i) {
if (i >= 3) {
ans[arr[i][1]] = (i + 1).ToString();
} else {
ans[arr[i][1]] = desc[i];
}
}
return ans;
}
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| var findRelativeRanks = function(score) {
const n = score.length;
const desc = ["Gold Medal", "Silver Medal", "Bronze Medal"];
const arr = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; ++i) {
arr[i][0] = score[i];
arr[i][1] = i;
}
arr.sort((a, b) => b[0] - a[0]);
const ans = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
if (i >= 3) {
ans[arr[i][1]] = '' + (i + 1);
} else {
ans[arr[i][1]] = desc[i];
}
}
return ans;
};
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
| class Solution:
desc = ("Gold Medal", "Silver Medal", "Bronze Medal")
def findRelativeRanks(self, score: List[int]) -> List[str]:
ans = [""] * len(score)
arr = sorted(enumerate(score), key=lambda x: -x[1])
for i, (idx, _) in enumerate(arr):
ans[idx] = self.desc[i] if i < 3 else str(i + 1)
return ans
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| var desc = [3]string{"Gold Medal", "Silver Medal", "Bronze Medal"}
func findRelativeRanks(score []int) []string {
n := len(score)
type pair struct{ score, idx int }
arr := make([]pair, n)
for i, s := range score {
arr[i] = pair{s, i}
}
sort.Slice(arr, func(i, j int) bool { return arr[i].score > arr[j].score })
ans := make([]string, n)
for i, p := range arr {
if i < 3 {
ans[p.idx] = desc[i]
} else {
ans[p.idx] = strconv.Itoa(i + 1)
}
}
return ans
}
|
复杂度分析
