字典應用: 排序映射過後的數值 Sort the Jumbled Numbers_LC #2191

Nick Fewings on Unsplash

題目敘述 Sort the Jumbled Numbers

給定兩個輸入陣列

第一個是映射表，提供0~9 mapping到新數字的映射關係。

第二個陣列是原始數值。

請重新排序原始數值，排序依據是根據映射表對應之後的新數值的大小決定。

如果對應之後的新數值大小相同，則由原本的前後相對順序決定。

測試範例

Example 1:

Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
Output: [338,38,991]
Explanation: 
991重新映射之後是669​
338重新映射之後是007
38重新映射之後是07
7 = 7 < 669

依照新數值的大小排序原本的數值
[338,38,991].

Example 2:

Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
Output: [123,456,789]
Explanation: 

789重新映射之後是789
456重新映射之後是456
123重新映射之後是123

123 < 456 < 789

依照新數值的大小排序原本的數值

[123,456,789].

演算法 映射新數值，依照新數值排序

根據題目敘述可以知道

排序有兩個條件

1. 依照映射後的新數值大小排序。
2. 如果新數值大小相同，則維持原本的前後相對順序。

因此，在產生新陣列時，放入排序所需的兩個資訊

# 新數值, 原本舊的index代表前後相對順序​
(mapped_num, index)

之後呼叫sort function從小到大排序，接著利用index去取回原有數值，依照順序輸出即可。

程式碼 映射新數值，依照新數值排序

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:

        new_value = []
      
        for index, num in enumerate(nums):

            # If the number is 0, get the mapped value for 0, else start with 0
            mapped_num = mapping[0] if num == 0 else 0
            power_of_ten = 1  # To keep track of the decimal place
          
           # Keep mapping new digit based on mapping table
            while num > 0:
                num, digit = divmod(num, 10)

                # Map the digit, adjust decimal place and add to the mapped number
                mapped_num = mapping[digit] * power_of_ten + mapped_num
                power_of_ten *= 10  # Increase the decimal place
          
            # Append the tuple of mapped number and original index to the list
            new_value.append((mapped_num, index))
      
        # Sort the list according to the mapped numbers, stable for identical values
        new_value.sort()
      
        # Reconstruct the sorted list using the original indices
        return [nums[i] for _, i in new_value]

複雜度分析

時間複雜度: O( n log n)

掃描每個數值，映射到新數值耗費O(n)

排序新數值耗費O(n log n)

比較重的成本是排序的O( n log n)

空間複雜度: O( n )

會需要一個儲存 新數值 與 舊數值的new_value陣列，所需空間為O(n)

Reference

[1] Sort the Jumbled Numbers - LeetCode