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]

上图中，我们可以先想像使用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