列表

详情

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

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

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

另外给你一个整数数组 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] 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) { } };

golang 解法, 执行用时: 456 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-07 10:48:43 

func sortJumbled(mapping []int, nums []int) []int {
    convert := func(num int) int {
        if num == 0 {
            return mapping[0]
        }
        target := 0
        pos := 1
        for num != 0 {
            target += mapping[num%10]*pos
            pos *= 10
            num /= 10
        }
        return target
    }
    
    sort.SliceStable(nums, func(i, j int) bool {
        return convert(nums[i]) < convert(nums[j])
    })

    return nums
}

java 解法, 执行用时: 91 ms, 内存消耗: 53.6 MB, 提交时间: 2023-09-07 10:48:05 

class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        int[] res = new int[nums.length];
        int[][] temp = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            temp[i][0] = nums[i];
            temp[i][1] = convert(mapping, nums[i]);
        }
        Arrays.sort(temp, new Comparator<int[]>() {
           public int compare(int[] a, int[] b) {
               return a[1] - b[1]; 
           } 
        });
        for (int i = 0; i < nums.length; i++) {
            res[i] = temp[i][0];
        }
        return res;
    }
    public int convert(int[] mapping, int val) {
        int digit = 1;
        int ret = 0;
        if (val <= 9) {
            return mapping[val];
        }
        while (val > 0) {
            ret += mapping[val % 10] * digit;
            digit *= 10;
            val /= 10;
        }
        return ret;
    }
}

cpp 解法, 执行用时: 636 ms, 内存消耗: 196.9 MB, 提交时间: 2023-09-07 10:47:36 

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;
    }
};

python3 解法, 执行用时: 936 ms, 内存消耗: 24 MB, 提交时间: 2023-09-07 10:47:02 

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

python3 解法, 执行用时: 328 ms, 内存消耗: 21.9 MB, 提交时间: 2023-09-07 10:46:35 

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        # 制作翻译表
        tab = str.maketrans("0123456789", "".join(map(str, mapping)))
        # 自定义排序: (num2map,idx)
        return sorted(nums, key=lambda x: int(str(x).translate(tab)))

上一题

© 2024 leetcode.cn