iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
Software Development

我在刷LeetCode時邂逅了Python系列 第 8

Day 8:506. Relative Ranks

今日題目

題目連結: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]

https://ithelp.ithome.com.tw/upload/images/20210922/20141336u4LD01rE12.png

上圖中,我們可以先想像使用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放進去
    https://ithelp.ithome.com.tw/upload/images/20210922/20141336bBpLxFGDZW.png

  2. 開始建立mapScore的資料,每次從heapScore中取得目前最小的數字,放入scoreMap中。每次建立出的資料方框,上面為Key = 分數、下面為Value = 名次,參考下圖中 step1 ~ step5。
    https://ithelp.ithome.com.tw/upload/images/20210922/201413361eS4wQztXU.png

  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


上一篇
Day 7:225. Implement Stack using Queues
下一篇
Day 9:1046. Last Stone Weight
系列文
我在刷LeetCode時邂逅了Python30

尚未有邦友留言

立即登入留言