0506. 相对名次 #

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

题目大意 #

给出 n 名运动员的成绩，用数组 score 表示。

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

解题思路 #

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

代码 #

 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