題目敘述 Rank Transform of an Array
給定一個陣列arr，請根據數字的大小給予序號，序號值介於1~len( set(arr) )之間。
最大的數字給予最大的序號。次大的數字給予次大的序號。
...依此類推
最小的數字給予最小的序號1。
數字有可能重複出現，相同的數字給予相同的序號。
最後，請根據每個數字的大小輸出對應的序號陣列，返回作為答案。
測試範例
Example 1:
Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.
Example 2:
Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.
Example 3:
Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]
約束條件
Constraints:
0 <= arr.length <= 10^5
輸入陣列長度介於0~十萬之間。
-10^9 <= arr[i] <= 10^9
每個陣列元素介於負十億~正十億之間。
演算法 排序，根據數字大小給予序號
唯一要注意的細節是，題目有特別提醒，數字有可能會重複。
所以，排序前，記得先進行set()操作，透過建立集合，
去過濾額外重複出現，多餘的數字。
接著排序，根據數字從小到大，從1開始，分別給予對應的序號即可。
程式碼 排序，根據數字大小給予序號
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
# keep unique elements of array in ascending order
elements_ascending = sorted(set(arr))
# dictionary
# key : number
# value : rank
num_rank_dict = dict()
for index, num in enumerate(elements_ascending):
# rank = index + 1
num_rank_dict[num] = (index+1)
# give each number with its corresponding rank
result = [ num_rank_dict[num] for num in arr ]
return result
複雜度分析
時間複雜度: O(n log n)
最重的工作落在排序上，所需時間成本為O(n log n)
輸出序號的時間成本是O(n)，相對小。
空間複雜度: O(n)
需要有一個額外的陣列elements_ascending，去記錄排序好的數字。
Reference
[1] Rank Transform of an Array - LeetCode
關鍵知識點: 排序
根據題意，從「根據數字大小給予序號」這個要求，連想到排序Sorting，
算是一個基本的排序應用題。
