高手競技 比賽排名頒獎(排序應用) Leetcode_#506

Aditya Joshi on Unsplash

題目敘述

輸入給定一個整數陣列，分別代表每位運動員在比賽中的成績。

分數最高的給予金牌"Gold Medal"
分數次高的給予金牌"Silver Medal"
分數第三高的給予金牌"Bronze Medal"
剩餘的名次依照順序給予"4", "5", ..., "n" 的編號。

輸出時以字串陣列返回答案。

原本的英文題目敘述

測試範例

Example 1:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

Example 2:

Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The placements are [1st, 5th, 3rd, 2nd, 4th].

約束條件

Constraints:

• n == score.length

令n代表分數陣列的長度。

• 1 <= n <= 10^4

n介於 1 ~ 一萬之間。

• 0 <= score[i] <= 10^6

每位選手的分數介於0~一百萬之間。

• All the values in score are unique.

每位選手的分數都不同，不會有同分的情況。

演算法 排序

這題滿直覺的，題目已經保證不會有同分的情況。

因此，直接對分數進行排序，
冠軍拿金牌，亞軍拿銀牌，季軍拿銅牌，剩下的名次拿到對應的數字即可。

程式碼 排序

class Solution:
    def findRelativeRanks(self, nums):
    			
        # 對分數由大到小進行排序	
        place = sorted(nums, reverse = True)
        
        # 依照名次給對應的獎牌
        prize = ["Gold Medal", "Silver Medal", "Bronze Medal"] + list(map(str, range(4, len(nums) + 1)))
        
        # 依照每個選手的排名進行頒獎
        return map(dict(zip(place, prize)).get, nums)

複雜度分析

時間複雜度: O(n log n)

n個分數進行排序，所需時間為O( n log n)。

空間複雜度: O(n)

place 排名陣列, prize獎牌陣列, 和臨時的mapping table所需空間皆為 O(n)。

關鍵知識點

題目已經保證不會有同分的情況。

因此，直接對分數進行排序，

冠軍拿金牌，亞軍拿銀牌，季軍拿銅牌，剩下的名次拿到對應的數字即可。

Reference

[1] Relative Ranks - LeetCode