🆚大小有別 根據大小給予序號 Rank Transform of an Array_Leetcode #1331

undefined on Tenor

題目敘述 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，

算是一個基本的排序應用題。