Medium

题目描述

给你一个下标从 0 开始的整数数组 mapping，它表示一个混乱十进制系统的映射规则。mapping[i] = j 表示这个系统中数字 i 应该映射为数字 j。

一个整数的映射值是将整数中每个数字 i 替换为 mapping[i] 得到的新整数，对于所有 0 <= i <= 9。

同时给你另一个整数数组 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，即去掉前导零后的 7。
38 映射为 07，去掉前导零后也是 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^4
  • 0 <= nums[i] < 10^9

解题思路

这道题的核心思路是先将每个数字按照映射规则转换，然后进行稳定排序。

解题步骤：

  1. 数字映射转换：对于每个数字，我们需要逐位提取数字，然后根据mapping数组进行映射。可以通过不断除以10来提取每一位数字，然后用mapping数组进行转换。

  2. 构建排序键值对：为了保持相同映射值的元素的相对顺序（稳定排序），我们需要记录原始索引。创建一个包含(映射值, 原始索引, 原始数字)的三元组数组。

  3. 排序：根据映射值进行排序，如果映射值相同则按原始索引排序，这样就能保证稳定性。

  4. 提取结果：从排序后的三元组中提取原始数字。

时间复杂度分析：

  • 映射转换：O(n * log(max_num))，其中n是nums长度
  • 排序：O(n * log(n))
  • 总体：O(n * log(n))

这种方法简单直观，通过预处理映射值然后利用稳定排序的特性来解决问题。

代码实现

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        vector<tuple<long long, int, int>> mapped_nums;
        
        for (int i = 0; i < nums.size(); i++) {
            long long mapped_value = getMappedValue(nums[i], mapping);
            mapped_nums.push_back({mapped_value, i, nums[i]});
        }
        
        sort(mapped_nums.begin(), mapped_nums.end());
        
        vector<int> result;
        for (auto& [mapped_val, idx, original] : mapped_nums) {
            result.push_back(original);
        }
        
        return result;
    }
    
private:
    long long getMappedValue(int num, vector<int>& mapping) {
        if (num == 0) return mapping[0];
        
        long long mapped = 0;
        long long multiplier = 1;
        
        while (num > 0) {
            int digit = num % 10;
            mapped += mapping[digit] * multiplier;
            multiplier *= 10;
            num /= 10;
        }
        
        return mapped;
    }
};

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        def get_mapped_value(num):
            if num == 0:
                return mapping[0]
            
            mapped = 0
            multiplier = 1
            
            while num > 0:
                digit = num % 10
                mapped += mapping[digit] * multiplier
                multiplier *= 10
                num //= 10
            
            return mapped
        
        mapped_nums = []
        for i, num in enumerate(nums):
            mapped_value = get_mapped_value(num)
            mapped_nums.append((mapped_value, i, num))
        
        mapped_nums.sort()
        
        return [original for mapped_val, idx, original in mapped_nums]

public class Solution {
    public int[] SortJumbled(int[] mapping, int[] nums) {
        var mappedNums = new List<(long mappedValue, int index, int original)>();
        
        for (int i = 0; i < nums.Length; i++) {
            long mappedValue = GetMappedValue(nums[i], mapping);
            mappedNums.Add((mappedValue, i, nums[i]));
        }
        
        mappedNums.Sort();
        
        int[] result = new int[nums.Length];
        for (int i = 0; i < mappedNums.Count; i++) {
            result[i] = mappedNums[i].original;
        }
        
        return result;
    }
    
    private long GetMappedValue(int num, int[] mapping) {
        if (num == 0) return mapping[0];
        
        long mapped = 0;
        long multiplier = 1;
        
        while (num > 0) {
            int digit = num % 10;
            mapped += mapping[digit] * multiplier;
            multiplier *= 10;
            num /= 10;
        }
        
        return mapped;
    }
}

var sortJumbled = function(mapping, nums) {
    const mapNumber = (num) => {
        return parseInt(num.toString().split('').map(digit => mapping[parseInt(digit)]).join(''));
    };
    
    return nums.map((num, index) => ({ num, mapped: mapNumber(num), index }))
               .sort((a, b) => a.mapped - b.mapped || a.index - b.index)
               .map(item => item.num);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(n))其中 n 是 nums 的长度，主要消耗在排序操作上
空间复杂度O(n)需要额外的数组存储映射值和索引信息

相关题目