LC 506. 相对名次

题目描述

这是 LeetCode 上的 506. 相对名次 ,难度为 简单

给你一个长度为 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:

1
2
3
4
5
输入:score = [5,4,3,2,1]

输出:["Gold Medal","Silver Medal","Bronze Medal","4","5"]

解释:名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2:
1
2
3
4
5
输入:score = [10,3,8,9,4]

输出:["Gold Medal","5","Bronze Medal","Silver Medal","4"]

解释:名次为 [1st, 5th, 3rd, 2nd, 4th] 。

提示:

  • $n == score.length$
  • $1 <= n <= 10^4$
  • $0 <= score[i] <= 10^6$
  • $score$ 中的所有值 互不相同

模拟

根据题意,我们可以先对 score 数组进行拷贝并排序,利用分数各不相同,对排序数组中分值进行名次编号(存入哈希表),再利用名次编号构造答案。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
String[] ss = new String[]{"Gold Medal", "Silver Medal", "Bronze Medal"};
public String[] findRelativeRanks(int[] score) {
int n = score.length;
String[] ans = new String[n];
int[] clone = score.clone();
Arrays.sort(clone);
Map<Integer, Integer> map = new HashMap<>();
for (int i = n - 1; i >= 0; i--) map.put(clone[i], n - 1 - i);
for (int i = 0; i < n; i++) {
int rank = map.get(score[i]);
ans[i] = rank < 3 ? ss[rank] : String.valueOf(rank + 1);
}
return ans;
}
}

  • 时间复杂度:拷贝 score 数组的复杂度为 $O(n)$;对拷贝数组进行排序的复杂度为 $O(n\log{n})$;构造哈希表的复杂度为 $O(n)$;利用哈希表构造答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度:$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.506 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!