題目敘述 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].
演算法 映射新數值，依照新數值排序
根據題目敘述可以知道
排序有兩個條件
- 依照映射後的新數值大小排序。
- 如果新數值大小相同，則維持原本的前後相對順序。
因此，在產生新陣列時，放入排序所需的兩個資訊
# 新數值, 原本舊的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)
