将杂乱无章的数字排序

难度: Medium

给你一个下标从 0 开始的整数数组 mapping ，它表示一个十进制数的映射规则，mapping[i] = j 表示这个规则下将数位 i 映射为数位 j 。

一个整数 映射后的值 为将原数字每一个数位 i （0 <= i <= 9）映射为 mapping[i] 。

另外给你一个整数数组 nums ，请你将数组 nums 中每个数按照它们映射后对应数字非递减顺序排序后返回。

注意：

如果两个数字映射后对应的数字大小相同，则将它们按照输入中的 相对顺序 排序。
nums 中的元素只有在排序的时候需要按照映射后的值进行比较，返回的值应该是输入的元素本身。

示例 1：

输入：mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
输出：[338,38,991]
解释：
将数字 991 按照如下规则映射：
1. mapping[9] = 6 ，所有数位 9 都会变成 6 。
2. mapping[1] = 9 ，所有数位 1 都会变成 9 。
所以，991 映射的值为 669 。
338 映射为 007 ，去掉前导 0 后得到 7 。
38 映射为 07 ，去掉前导 0 后得到 7 。
由于 338 和 38 映射后的值相同，所以它们的前后顺序保留原数组中的相对位置关系，338 在 38 的前面。
所以，排序后的数组为 [338,38,991] 。

示例 2：

输入：mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
输出：[123,456,789]
解释：789 映射为 789 ，456 映射为 456 ，123 映射为 123 。所以排序后数组为 [123,456,789] 。

提示：

mapping.length == 10
0 <= mapping[i] <= 9
mapping[i] 的值 互不相同 。
1 <= nums.length <= 3 * 10⁴
0 <= nums[i] < 10⁹

Submission

运行时间: 251 ms

内存: 21.8 MB

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        mp = str.maketrans("0123456789","".join(map(str,mapping)))
        return sorted(nums,key = lambda x: int(str(x).translate(mp)))

Explain

这个解决方案通过创建一个数字映射表，将每个数字字符（'0'-'9'）映射到对应的新数字字符。这是通过使用 Python 的 str.maketrans 和 map 函数来实现的，生成一个转化表 mp。然后，使用 sorted 函数对 nums 数组进行排序，但排序的依据不是数字本身，而是每个数字转换后的结果。转换是通过将每个数字转为字符串，然后使用 translate 方法应用映射，最后转换回整数来比较。由于 Python 的 sorted 函数稳定（保持相等元素的相对顺序），因此如果两个数字映射后相等，它们会按照在原数组中的顺序排列。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        # 创建映射表，用于将每个数字字符转换到对应的新字符
        mp = str.maketrans("0123456789", "".join(map(str, mapping)))
        # 使用映射表对 nums 中的每个数字进行转换，并根据转换后的数字进行排序
        # sorted 是稳定的排序，因此相同的值将保持原始顺序
        return sorted(nums, key = lambda x: int(str(x).translate(mp)))

Explore

在函数 sortJumbled 中，数字首先需要转换成字符串，是因为 str.maketrans 和 translate 方法都是针对字符串操作的。数字本身不能直接被这些方法处理。通过将数字转换为字符串，我们可以对每个数位字符应用映射表，将其转换成对应的新数字字符。

映射表 mp 是通过 str.maketrans 方法创建的，该方法接收两个字符串：一个是原始字符集，另一个是目标字符集。在这种情况下，原始字符集是 '0123456789'，目标字符集是通过将 mapping 列表中的数字转换为字符串并连接起来生成的。这种对应关系确保每个数字字符 '0' 到 '9' 被正确地映射到它们在mapping列表中的对应数字。

在解题思路中提到的 '转换后的结果' 指的是每个数字在转换成字符串并且通过映射表 mp 处理后形成的新的数字字符串。这个新的数字字符串代表的整数，就是原始数字在映射表下的表示。排序函数 sorted 根据这个 '转换后的结果'（即映射后的整数值）来排序整个列表。这意味着数字的排序依据是它们映射后的数值，而不是原始数值。

sorted 函数是一个稳定的排序算法。这意味着如果两个元素在比较时被认为是相等的，它们会保持在原数组中的相对顺序不变。在 sortJumbled 函数中，如果两个数字映射后的结果相同，sorted 函数会保持它们在输入列表 nums 中的原始顺序，这是稳定排序的一个重要特性。