0506. 相对名次 #

标签：数组、排序、堆（优先队列）
难度：简单

题目大意 #

描述：给定一个长度为 n 的数组 score。其中 score[i] 表示第 i 名运动员在比赛中的成绩。所有成绩互不相同。

要求：找出他们的相对名次，并授予前三名对应的奖牌。前三名运动员将会被分别授予「金牌（Gold Medal）」，「银牌（Silver Medal）」和「铜牌（Bronze Medal）」。

说明：

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

示例：

1
2
3
4
5
6
7
8


输入：score = [5,4,3,2,1]
输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。


输入：score = [10,3,8,9,4]
输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"]
解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。

解题思路 #

思路 1：排序 #

先对数组 score 进行排序。
再将对应前三个位置上的元素替换成对应的字符串：Gold Medal, Silver Medal, Bronze Medal。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution:
    def shellSort(self, arr):
        size = len(arr)
        gap = size // 2

        while gap > 0:
            for i in range(gap, size):
                temp = arr[i]
                j = i
                while j >= gap and arr[j - gap] < temp:
                    arr[j] = arr[j - gap]
                    j -= gap
                arr[j] = temp
            gap = gap // 2
        return arr

    def findRelativeRanks(self, score: List[int]) -> List[str]:
        nums = score.copy()
        nums = self.shellSort(nums)
        score_map = dict()
        for i in range(len(nums)):
            score_map[nums[i]] = i + 1

        res = []
        for i in range(len(score)):
            if score[i] == nums[0]:
                res.append("Gold Medal")
            elif score[i] == nums[1]:
                res.append("Silver Medal")
            elif score[i] == nums[2]:
                res.append("Bronze Medal")
            else:
                res.append(str(score_map[score[i]]))
        return res

思路 1：复杂度分析 #

时间复杂度：$O(n \times \log_2n)$。因为采用了时间复杂度为 $O(n \times \log_2n)$ 的希尔排序。
空间复杂度：$O(n)$。