506. 相对名次 : 简单排序模拟题

题目描述

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

Tag : 「排序」、「模拟」

给你一个长度为 n 的整数数组 score，其中 score[i] 是第 ii 位运动员在比赛中的得分。所有得分都互不相同。

运动员将根据得分决定名次，其中名次第 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.lengthn==score.length
• 1 <= n <= 10^41<=n<=104
• 0 <= score[i] <= 10^60<=score[i]<=106
• scorescore 中的所有值 互不相同

模拟

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

代码：

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)；对拷贝数组进行排序的复杂度为 O(n\log{n})O(nlogn)；构造哈希表的复杂度为 O(n)O(n)；利用哈希表构造答案复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
• 空间复杂度：O(n)O(n)

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

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