題目敘述
輸入給定一個整數陣列，分別代表每位運動員在比賽中的成績。
分數最高的給予金牌"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
scoreare 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)。
關鍵知識點
題目已經保證不會有同分的情況。
因此，直接對分數進行排序，
冠軍拿金牌，亞軍拿銀牌，季軍拿銅牌，剩下的名次拿到對應的數字即可。
