⚡Flashcard Drill➔
NeetCode #149LC-2191MediumArrays & Hashing
← Back to All Problems

#149 · #2191 · Sort the Jumbled Numbers(将杂乱数组排序)

📌 Problem Statement & Constraints

You are given a 0-indexed integer array nums and an array mapping of 10 digits. The mapped value of a number is obtained by replacing each digit d with mapping[d]. Sort nums by mapped value ascending, breaking ties by the original index. Constraints: 1 <= nums.length <= 3 * 10^4, 0 <= nums[i] < 10^9, mapping.length == 10.

💡 Core Algorithmic Approaches

  1. Compute the mapped value for each number once, then sort the indices by (mapped_value, original_index).
  2. The mapped value is built by processing the digits in order and appending mapping[digit].
  3. Sorting indices rather than the values themselves preserves the original element for the output.
  4. Ties must be broken by the original index, which a stable sort would also achieve -- but stating the index in the key is explicit and safe.

💻 Benchmark Python3 Implementation

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        def mapped(x: int) -> int:
            return int("".join(str(mapping[int(d)]) for d in str(x)))

        order = sorted(range(len(nums)), key=lambda i: (mapped(nums[i]), i))
        return [nums[i] for i in order]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * L log n) where L is the number of digits: each comparison needs the mapped value, so precomputing it (as the key function does, once per element) keeps this at O(n * L + n log n).
💾 Space Complexity
O(n) for the index list and the sort's internal storage.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the tie-break on the original index: the problem requires ties to preserve the original order.
  • Leading zeros in the mapped value: mapping may map a digit to 0, and int() drops leading zeros, which is correct -- the mapped value is a number, not a string.
  • Recomputing the mapped value inside a comparator: O(n log n * L) instead of O(n * L); use a key function so each value is computed once.
  • Sorting the numbers themselves: you would lose the ability to break ties by the original index unless you carry it along.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems

中文速览与面试要点

将杂乱数组排序

给你一个下标从 0 开始的整数数组 mapping,它表示一个十进制数的映射规则: mapping[i] 表示数字 i 映射到的值。给你一个整数数组 nums,请你将 nums 中每个元素按以下方式转换为新的值:把元素的每一位数字按 mapping 映射后,拼接成一个新的十进制数。请按照映射后的值 升序 对 nums 排序,若映射后的值相同则保持原有的相对顺序(稳定排序)。返回排序后的 nums。约束:mapping.length == 10;0 ≤ mapping[i] ≤ 9;1 ≤ nums.length ≤ 3 × 10^4;0 ≤ nums[i] ≤ 10^9。

核心要点

  • 映射 + 稳定排序(标准解) :定义一个 mapped(x) 函数,把 x 的每一位按 mapping 替换后重新组成整数;然后用它作为 sorted 的 key。
  • Python 的 sorted 天然稳定 :映射值相同时会保持原数组中的相对顺序,无需额外处理。
  • 边界:x == 0 :0 只有一位数字,映射后为 mapping[0] ,必须特判(否则 while 循环不执行,会返回 0)。
  • 逐位处理 : x % 10 取出最低位, x //= 10 右移,收集后反转。注意前导零——映射后可能产生前导零(如 mapping[0] = 0 时),拼接成整数时前导零自然消失,这正是题目要求的。

常见陷阱

  • 忘记特判 x == 0 : while x: 对 0 不执行,会返回初始值 0 而非 mapping[0] 。
  • 用不稳定的排序 :题目要求映射值相同时保持原相对顺序,必须用稳定排序。Python 的 sorted 天然稳定;若用 heapq 等不稳定结构需额外记录原下标。
  • 把映射结果当字符串比较 :映射后可能产生前导零,字符串比较(如 "01" vs "1")与数值比较结果不同。必须先转成整数。
  • 重建时顺序颠倒 : x % 10 先得到最低位,因此必须 reversed 后才能正确重建高位到低位。

参考实现

class Solution:
    def sortJumbled(self, mapping: list[int], nums: list[int]) -> list[int]:
        def mapped(x: int) -> int:
            if x == 0:
                return mapping[0]           # 特判 0
            digits = []
            while x:
                digits.append(x % 10)
                x //= 10
            res = 0
            for d in reversed(digits):      # 从高位到低位重建
                res = res * 10 + mapping[d]
            return res

        # sorted 是稳定排序:映射值相同时保持原有相对顺序
        return sorted(nums, key=mapped)