2191-将杂乱无章的数字排序

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你一个下标从 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 都会变成 8 。
所以，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 * 104
  • 0 <= nums[i] < 109

方法一：自定义排序

思路与算法

对于每一个数而言，我们可以先把它转换成数位列表，例如将 345 变为 [3,4,5]，然后通过给定的映射规则 mapping 将其映射，最后再从数位列表恢复成一个数。

记上述的转换过程为函数 transfer，那么对于数组 nums 中的每一个元素 nums}[i]，我们构建二元组 (\textit{transfer}(\textit{nums}[i]), \textit{nums}[i])，那么在排序时，我们只需要根据二元组中 transfer}(\textit{nums}[i]) 进行升序排序即可。

注意到题目中要求「如果两个数字映射后对应的数字大小相同，则将它们按照输入中的相对顺序排序」，因此如果使用的语言中提供了稳定排序，那么我们可以直接使用稳定排序；如果没有提供稳定排序，那么需要使用三元组 (\textit{transfer}(\textit{nums}[i]), i, \textit{nums}[i]) 代替之前的二元组，并按照 transfer}(\textit{nums}[i]) 为第一关键字、i 为第二关键字进行升序排序，这样就能满足题目中的要求。

在排序结束后，我们从二元组（或三元组）中提取出原始的元素并组成列表，即可得到最终的答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        auto transfer = [&](int x) -> int {
            if (x == 0) {
                return mapping[0];
            }
            
            vector<int> digits;
            while (x) {
                digits.push_back(x % 10);
                x /= 10;
            }
            int num = 0;
            for (int i = digits.size() - 1; i >= 0; --i) {
                num = num * 10 + mapping[digits[i]];
            }
            return num;
        };
        
        vector<pair<int, int>> num_pairs;
        for (int num: nums) {
            num_pairs.emplace_back(transfer(num), num);
        }
        stable_sort(num_pairs.begin(), num_pairs.end(), [](const auto& lhs, const auto& rhs) {
            return lhs.first < rhs.first;
        });

        vector<int> ans;
        for (const auto& [_, num]: num_pairs) {
            ans.push_back(num);
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        def transfer(x: int) -> int:
            return int("".join(str(mapping[int(digit)]) for digit in str(x)))
        
        num_pairs = [(transfer(num), num) for num in nums]
        num_pairs.sort(key=lambda pair: pair[0])
        
        ans = [num for (_, num) in num_pairs]
        return ans

复杂度分析

  • 时间复杂度：O(n (\log n + \log C))，其中 n 是数组 nums 的长度，C 是数组 nums 中的元素范围，\log C 即为元素的位数。

    • 计算所有映射需要的时间为 O(n \log C)；

    • 排序需要的时间为 O(n \log n)；

    • 构造答案需要的时间为 O(n)。

  • 空间复杂度：O(n)，即为存储二元组（或三元组）需要的空间。

 Comments
On this page
2191-将杂乱无章的数字排序