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
- Compute the mapped value for each number once, then sort the indices by
(mapped_value, original_index). - The mapped value is built by processing the digits in order and appending
mapping[digit]. - Sorting indices rather than the values themselves preserves the original element for the output.
- 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:
mappingmay map a digit to 0, andint()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
keyfunction 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.
🧩 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)