What is the key pattern in the Sort the Jumbled Numbers problem?

The problem revolves around transforming numbers using a custom mapping and sorting them based on these mapped values, combining array manipulation and sorting techniques.

How does mapping affect the sorting order in this problem?

The sorting order is determined by the transformed (mapped) values of the numbers. The key is to ensure that numbers with the same mapped value maintain their relative order from the original array.

What are the time and space complexities of solving this problem?

The time complexity is O(n log n) due to the sorting operation, and the space complexity is O(n) for storing the mapped values before sorting.

Can this problem be solved without sorting?

Sorting is essential in this problem because the goal is to return the numbers in non-decreasing order based on their mapped values, so sorting is the most direct approach.

What are some common mistakes when solving the Sort the Jumbled Numbers problem?

Common mistakes include failing to correctly map the digits, not maintaining the stability of sorting for equal mapped values, and using inefficient algorithms for large inputs.

#2191

Medium

auto_awesome数组·排序

LeetCode 题解工作台

将杂乱无章的数字排序

给你一个下标从 0 开始的整数数组 mapping ，它表示一个十进制数的映射规则， mapping[i] = j 表示这个规则下将数位 i 映射为数位 j 。一个整数映射后的值为将原数字每一个数位 i （ 0 ）映射为 mapping[i] 。另外给你一个整数数组 nums ，请你将数组 …

数组排序

题目描述

给你一个下标从 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⁹

lightbulb

解题思路

方法一：自定义排序

我们遍历数组 $nums$ 中的每个元素 $nums[i]$ ，将其映射后的值 $y$ 与下标 $i$ 一起存入数组 $arr$ 中，然后对数组 $arr$ 进行排序，最后将排序后的数组 $arr$ 中的下标 $i$ 取出，转换为原数组 $nums$ 中的元素 $nums[i]$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        def f(x: int) -> int:
            if x == 0:
                return mapping[0]
            y, k = 0, 1
            while x:
                x, v = divmod(x, 10)
                v = mapping[v]
                y = k * v + y
                k *= 10
            return y

        arr = sorted((f(x), i) for i, x in enumerate(nums))
        return [nums[i] for _, i in arr]

speed

复杂度分析

指标	值
时间	O(n\cdot \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for candidates who understand how mapping and sorting can be combined for a custom sorting problem.
question_mark
Candidates should demonstrate understanding of stability in sorting, ensuring that equal mapped values preserve their relative order.
question_mark
Expect candidates to efficiently handle mapping transformations and sorting of numbers in non-decreasing order.

warning

常见陷阱

外企场景

error
Misunderstanding the mapping transformation and mistakenly modifying the original numbers without mapping their digits first.
error
Not maintaining the relative order of numbers when their mapped values are the same, causing incorrect sorting results.
error
Inefficient mapping and sorting logic, leading to higher time complexity than the expected O(n log n).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the length of the nums array to test performance under larger inputs.
arrow_right_alt
Adjusting the mapping to include digits in reverse order or with repeated values, affecting the mapping logic.
arrow_right_alt
Providing edge cases where nums contains a single element or multiple elements with identical mapped values.

help

常见问题

外企场景

继续练习

#2195 向数组中追加 K 个整数 #2171 拿出最少数目的魔法豆 #2164 对奇偶下标分别排序