今日題目

題目連結：506. Relative Ranks
題目主題：Array, Sorting, Heap(Priority Queue)

前幾天結束了Stack及Queue以後，接下來進入新的主題是 Heap(Priority Queue)，我認為這是非常方便好用的資料結構。

簡單說說 Heap(Priority Queue)

Heap又稱Priority Queue，講到這個可能會開始牽扯樹（tree）的概念，不過暫時不提樹（tree），只要先瞭解怎麼使用它即可，Heap大致分成兩種 Max Heap 及 Min Heap，以下範例使用 Min Heap 來看看取資料的過程：

範例資料：nums = [13, 14, 11, 1, 4, 6, 16]

上圖中，我們可以先想像使用Heap時，就像是把這個 nums 亂數資料都丟進一個箱子，Min Heap 取資料原則就是每一次一定會優先取得最小值。相反的，如果是 Max Heap 的話原則就是每次一定會優先取得最大值。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

本題會輸入一個score的列表，每一個分數代表著一個運動員的分數，每個分數一定會是唯一的。目標是回傳一個新的字串列表，列表會是每個運動員的名次，最高分數為第一名，顯示方式如下：

1. 第一名字串為 "Gold Medal"。
2. 第二名字串為 "Silver Medal"。
3. 第三名字串為 "Bronze Medal"。
4. 第四名之後的名次，直接以數字表示，如 "4", "5", "6"

約束：

• n == score.length
• 1 <= n <= 104
• 0 <= score[i] <= 106
• 所有在score中的值都是唯一的

範例1

輸入: score = [5,4,3,2,1]
輸出: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
解釋: 依名次排名 5 是最高分所以是第一名，1 最低分所以是最後一名，最終排名是 [1st, 2nd, 3rd, 4th, 5th]，可以看到輸出的結果，1, 2, 3 分別為指定字串，4, 5直接輸出字串數字。

範例2

輸入: score = [10,3,8,9,4]
輸出: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
解釋: 此範例排完名次會像是這樣 [1st, 5th, 3rd, 2nd, 4th]，在輸出的列表時並不會改變順序，是依照對應的位置來輸出字串列表。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告一個mapScore，這是一個存放分數對應名次的map，Ex： Key = 分數, Value = 名次。
2. 宣告一個heapScore，將輸入的score複製到裡面，並轉成min-heap的結構。
3. 使用min-heap方式來實作，因此跑一個迴圈，從最後一名開始走：
   • 每次取出目前最後一名，標好名次放進第 1 步驟準備好的map中
4. 最後利用第 1 步驟準備好的map，將score分數列表轉成字串的名字列表輸出。

圖解過程

範例：score = [10, 3, 8, 9, 4]

1. 宣告一個 mapScore 及 heapScore
   mapScore：存放分數對應的名次
   heapScore：將輸入的score轉成heap放進去
   

2. 開始建立mapScore的資料，每次從heapScore中取得目前最小的數字，放入scoreMap中。每次建立出的資料方框，上面為Key = 分數、下面為Value = 名次，參考下圖中 step1 ~ step5。
   

3. 上圖中的最後步驟 step6，是score利用mapScore去對應出最後輸出的名次列表。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

# python 可直接使用 heapq 來實現 heap，預設為 min-heap
from heapq import heapify, heappop 

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        # 存放 key = 分數,value = 名次 的map
        mapScore = {} 
        # 將分數轉為 heap 資料結構
        heapScore =  score[:]
        heapify(heapScore)
        
        # 使用 min-heap 實作，因此從最後一名開始走
        rank = len(score)
        while rank > 0:
            # 每一次取得目前最後一名
            num = heappop(heapScore)
            # 依照名次來指定字串 放進map中
            if rank == 1: mapScore[num] = 'Gold Medal'
            elif rank == 2: mapScore[num] = 'Silver Medal'
            elif rank == 3: mapScore[num] = 'Bronze Medal'
            else: mapScore[num] = str(rank)
            rank -= 1
        # 將分數列表轉為名次列表輸出
        return [mapScore[num] for num in score]

希望您今天能瞭解到...

1. Heap(Priority Queue) 的基本概念
2. 506. Relative Ranks 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：1046. Last Stone Weight