LeetCode 2191「Sort the Jumbled Numbers」全解映射值排序的两种实现与陷阱NeetCode 题解仓库实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 articles/sort-the-jumbled-numbers.md 为核心骨架结合本仓库GitHub 推荐项目精选 / leetcode1 / leetcodeLeetCode 多语言题解集的多语言实现范式系统讲解 LeetCode 2191「Sort the Jumbled Numbers」如何根据「数字 → 映射数字」规则把每个数换算成映射值再按映射值稳定排序并返回原数组。读完你将掌握「字符串逐位映射 排序」与「纯算术逐位映射 排序」两种解法理解自定义比较器、稳定排序、数字位操作在真实题解中的配合方式并避开 0 值特判、不稳定排序、整数溢出三大经典坑点。前置知识Prerequisites在动手实现该题之前建议先牢固掌握以下四块基础能力它们直接决定解题代码的质量自定义比较器Custom Comparators编写比较函数来定义自定义的排序规则。本仓库的 sort-an-array.md 展示了快速排序、归并排序、堆排序等经典排序实现可作为自定义排序逻辑的对比参考。数字位操作Digit Manipulation使用取模modulo与整除division提取、转换单个数字例如n % 10取末位、n // 10去掉末位。稳定排序Stable Sorting理解稳定排序会保持相等元素的原始相对顺序——这正是本题「映射值相等时按原数组顺序输出」的关键。字符串 / 数字转换String/Number Conversion能在数字表示与字符串表示之间自由转换如str(n)/int(c)、String.valueOf/to_string等。题目本质把「排序键」先算出来题目的输入是一个长度为 10 的mapping数组mapping[digit]表示数字digit被替换成的数字以及待排序数组nums。核心流程只有三步对nums中每个数逐位用mapping替换拼出该数的映射值mapped value按映射值对原数组做稳定排序映射值相等时保持原相对顺序输出排序后的原数值不是映射值。也就是说映射值只是排序用的「键」最终答案里放的是原来的数。因此「保存 (映射值, 原下标) 二元组」是贯穿两种解法的共同结构。解法一字符串转换 排序Convert To Strings Sorting直觉Intuition把每个数先转成字符串就可以轻松地逐字符遍历它的每一位查表mapping得到映射后的数字边遍历边把映射值累乘 10 再累加从而构造出映射值。为了让映射值相等的元素保持原相对顺序我们在保存(映射值, 原下标)二元组后依赖排序的稳定性来完成这一约束。算法步骤Algorithm遍历输入数组中的每个数将其转换为字符串逐字符遍历该字符串查mapping表得到映射数字通过「先乘 10 再加」的方式构造mapped值为每个数保存(mapped, 原下标)二元组按mapped值对二元组排序——由于稳定排序特性mapped值相等的元素保持原数组中的相对顺序利用保存的下标从原数组中取回数值构造并返回结果数组。多语言实现class Solution: def sortJumbled(self, mapping: List[int], nums: List[int]) - List[int]: pairs [] for i, n in enumerate(nums): n str(n) mapped_n 0 for c in n: mapped_n * 10 mapped_n mapping[int(c)] pairs.append((mapped_n, i)) pairs.sort() return [nums[p[1]] for p in pairs]public class Solution { public int[] sortJumbled(int[] mapping, int[] nums) { int n nums.length; int[][] pairs new int[n][2]; for (int i 0; i n; i) { String numStr String.valueOf(nums[i]); int mapped_n 0; for (char c : numStr.toCharArray()) { mapped_n mapped_n * 10 mapping[c - 0]; } pairs[i][0] mapped_n; pairs[i][1] i; } Arrays.sort(pairs, (a, b) - a[0] - b[0]); int[] res new int[n]; for (int i 0; i n; i) { res[i] nums[pairs[i][1]]; } return res; } }class Solution { public: vectorint sortJumbled(vectorint mapping, vectorint nums) { vectorpairint, int pairs; for (int i 0; i nums.size(); i) { string numStr to_string(nums[i]); int mapped_n 0; for (char c : numStr) { mapped_n mapped_n * 10 mapping[c - 0]; } pairs.push_back({mapped_n, i}); } sort(pairs.begin(), pairs.end()); vectorint res; for (auto p : pairs) { res.push_back(nums[p.second]); } return res; } };class Solution { /** * param {number[]} mapping * param {number[]} nums * return {number[]} */ sortJumbled(mapping, nums) { let pairs []; for (let i 0; i nums.length; i) { let numStr nums[i].toString(); let mapped_n 0; for (let c of numStr) { mapped_n mapped_n * 10 mapping[parseInt(c)]; } pairs.push([mapped_n, i]); } pairs.sort((a, b) a[0] - b[0]); return pairs.map((p) nums[p[1]]); } }public class Solution { public int[] SortJumbled(int[] mapping, int[] nums) { int n nums.Length; int[][] pairs new int[n][]; for (int i 0; i n; i) { string numStr nums[i].ToString(); int mapped_n 0; foreach (char c in numStr) { mapped_n mapped_n * 10 mapping[c - 0]; } pairs[i] new int[] { mapped_n, i }; } Array.Sort(pairs, (a, b) a[0].CompareTo(b[0])); int[] res new int[n]; for (int i 0; i n; i) { res[i] nums[pairs[i][1]]; } return res; } }func sortJumbled(mapping []int, nums []int) []int { n : len(nums) pairs : make([][2]int, n) for i, num : range nums { numStr : strconv.Itoa(num) mapped_n : 0 for _, c : range numStr { mapped_n mapped_n*10 mapping[c-0] } pairs[i] [2]int{mapped_n, i} } sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] pairs[j][0] }) res : make([]int, n) for i, p : range pairs { res[i] nums[p[1]] } return res }class Solution { fun sortJumbled(mapping: IntArray, nums: IntArray): IntArray { val n nums.size val pairs Array(n) { intArrayOf(0, 0) } for (i in 0 until n) { val numStr nums[i].toString() var mapped_n 0 for (c in numStr) { mapped_n mapped_n * 10 mapping[c - 0] } pairs[i] intArrayOf(mapped_n, i) } pairs.sortBy { it[0] } return IntArray(n) { nums[pairs[it][1]] } } }class Solution { func sortJumbled(_ mapping: [Int], _ nums: [Int]) - [Int] { let n nums.count var pairs [(Int, Int)]() for i in 0..n { let numStr String(nums[i]) var mapped_n 0 for c in numStr { mapped_n mapped_n * 10 mapping[Int(String(c))!] } pairs.append((mapped_n, i)) } pairs.sort { $0.0 $1.0 } return pairs.map { nums[$0.1] } } }impl Solution { pub fn sort_jumbled(mapping: Veci32, nums: Veci32) - Veci32 { let n nums.len(); let mut pairs: Vec(i32, usize) Vec::with_capacity(n); for i in 0..n { let num_str nums[i].to_string(); let mut mapped_n 0; for c in num_str.bytes() { mapped_n mapped_n * 10 mapping[(c - b0) as usize]; } pairs.push((mapped_n, i)); } pairs.sort_by_key(|p| p.0); pairs.iter().map(|p| nums[p.1]).collect() } }复杂度分析时间复杂度$O(n \log n)$主导项为排序映射值的构造为 $O(n \times d)$其中 $d$ 为数字位数在本题量级下被排序复杂度覆盖空间复杂度$O(n)$存储(映射值, 下标)二元组解法二数字迭代 排序Iterate On Numbers Sorting直觉Intuition字符串转换虽然直观但会引入额外的字符串对象开销。解法二直接用算术运算提取数字反复用n % 10取出末位、映射后乘以当前位权base累加再用n // 10去掉末位同时base * 10提升位权。这样完全规避了字符串转换得到相同的排序结果。算法步骤Algorithm对每个数初始化mapped 0、base 1特判 0当n 0时直接令mapped mapping[0]因为后续的 while 循环对 0 不会执行否则循环digit n % 10取末位 →mapped base * mapping[digit]→n // 10→base * 10直至n 0保存(mapped, 原下标)二元组按mapped值排序用保存的下标还原原数组。多语言实现class Solution: def sortJumbled(self, mapping: List[int], nums: List[int]) - List[int]: pairs [] for i, n in enumerate(nums): mapped_n 0 base 1 if n 0: mapped_n mapping[0] else: while n 0: digit n % 10 n // 10 mapped_n base * mapping[digit] base * 10 pairs.append((mapped_n, i)) pairs.sort() return [nums[p[1]] for p in pairs]public class Solution { public int[] sortJumbled(int[] mapping, int[] nums) { int n nums.length; int[][] pairs new int[n][2]; for (int i 0; i n; i) { int mapped_n 0, base 1; int num nums[i]; if (num 0) { mapped_n mapping[0]; } else { while (num 0) { int digit num % 10; num / 10; mapped_n base * mapping[digit]; base * 10; } } pairs[i][0] mapped_n; pairs[i][1] i; } Arrays.sort(pairs, (a, b) - Integer.compare(a[0], b[0])); int[] res new int[n]; for (int i 0; i n; i) { res[i] nums[pairs[i][1]]; } return res; } }class Solution { public: vectorint sortJumbled(vectorint mapping, vectorint nums) { vectorpairint, int pairs; for (int i 0; i nums.size(); i) { int mapped_n 0, base 1; int num nums[i]; if (num 0) { mapped_n mapping[0]; } else { while (num 0) { int digit num % 10; num / 10; mapped_n base * mapping[digit]; base * 10; } } pairs.push_back({mapped_n, i}); } sort(pairs.begin(), pairs.end()); vectorint res; for (auto p : pairs) { res.push_back(nums[p.second]); } return res; } };class Solution { /** * param {number[]} mapping * param {number[]} nums * return {number[]} */ sortJumbled(mapping, nums) { let pairs []; for (let i 0; i nums.length; i) { let mapped_n 0, base 1; let num nums[i]; if (num 0) { mapped_n mapping[0]; } else { while (num 0) { let digit num % 10; num Math.floor(num / 10); mapped_n base * mapping[digit]; base * 10; } } pairs.push([mapped_n, i]); } pairs.sort((a, b) a[0] - b[0]); return pairs.map((p) nums[p[1]]); } }public class Solution { public int[] SortJumbled(int[] mapping, int[] nums) { int n nums.Length; int[][] pairs new int[n][]; for (int i 0; i n; i) { int mapped_n 0, base_val 1; int num nums[i]; if (num 0) { mapped_n mapping[0]; } else { while (num 0) { int digit num % 10; num / 10; mapped_n base_val * mapping[digit]; base_val * 10; } } pairs[i] new int[] { mapped_n, i }; } Array.Sort(pairs, (a, b) a[0].CompareTo(b[0])); int[] res new int[n]; for (int i 0; i n; i) { res[i] nums[pairs[i][1]]; } return res; } }func sortJumbled(mapping []int, nums []int) []int { n : len(nums) pairs : make([][2]int, n) for i, num : range nums { mapped_n, base : 0, 1 if num 0 { mapped_n mapping[0] } else { for num 0 { digit : num % 10 num / 10 mapped_n base * mapping[digit] base * 10 } } pairs[i] [2]int{mapped_n, i} } sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] pairs[j][0] }) res : make([]int, n) for i, p : range pairs { res[i] nums[p[1]] } return res }class Solution { fun sortJumbled(mapping: IntArray, nums: IntArray): IntArray { val n nums.size val pairs Array(n) { intArrayOf(0, 0) } for (i in 0 until n) { var mapped_n 0 var base 1 var num nums[i] if (num 0) { mapped_n mapping[0] } else { while (num 0) { val digit num % 10 num / 10 mapped_n base * mapping[digit] base * 10 } } pairs[i] intArrayOf(mapped_n, i) } pairs.sortBy { it[0] } return IntArray(n) { nums[pairs[it][1]] } } }class Solution { func sortJumbled(_ mapping: [Int], _ nums: [Int]) - [Int] { let n nums.count var pairs [(Int, Int)]() for i in 0..n { var mapped_n 0 var base 1 var num nums[i] if num 0 { mapped_n mapping[0] } else { while num 0 { let digit num % 10 num / 10 mapped_n base * mapping[digit] base * 10 } } pairs.append((mapped_n, i)) } pairs.sort { $0.0 $1.0 } return pairs.map { nums[$0.1] } } }impl Solution { pub fn sort_jumbled(mapping: Veci32, nums: Veci32) - Veci32 { let n nums.len(); let mut pairs: Vec(i32, usize) Vec::with_capacity(n); for i in 0..n { let mut mapped_n 0; let mut base 1; let mut num nums[i]; if num 0 { mapped_n mapping[0]; } else { while num 0 { let digit (num % 10) as usize; num / 10; mapped_n base * mapping[digit]; base * 10; } } pairs.push((mapped_n, i)); } pairs.sort_by_key(|p| p.0); pairs.iter().map(|p| nums[p.1]).collect() } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$两种解法对比维度解法一字符串转换解法二算术迭代逐位获取方式字符串逐字符遍历% 10取末位、/ 10去末位构造顺序从最高位开始高位先乘 10从最低位开始低位先乘base0 值特判不需要0的循环自然处理必须while 循环不执行额外开销字符串对象分配无纯整数运算时间复杂度$O(n \log n)$$O(n \log n)$常见陷阱Common Pitfalls陷阱一算术解法中未特判 0使用算术方式提取数字时数字 0 必须单独处理循环while (n 0)对 0 一次都不会执行导致mapped值停留在初始值若初始化为 0 会得到错误结果若未初始化则是未定义行为。必须显式判断n 0并直接使用mapping[0]。在 Python 中还需注意while n 0之后n已被整除为 0因此循环内应使用临时变量或在循环前保存原始值。陷阱二使用不稳定排序且不记录原始顺序题目明确要求「映射值相等的元素保持原相对顺序」。如果只保存映射值而丢弃原下标再使用不稳定排序例如部分语言中未指定稳定性的sort实现当多个数映射到同一值时输出顺序将与要求不符。可靠的解法是保存(映射值, 原下标)二元组稳定排序天然满足要求即使排序本身不稳定按二元组整体排序先比较映射值、再比较下标也能保证正确。这也正是两种解法中统一采用「二元组 排序」模式的原因。陷阱三构造映射值时的整数溢出对于很大的输入数字映射值可能溢出。Python 等具备任意精度整数的语言天然免疫但在 Java、C 等固定宽度整数语言中务必结合题目给定的最大输入约束判断mapped_n mapped_n * 10 mapping[digit]是否超出int范围必要时改用long。JavaScript 中则需注意parseInt/Number对超大整数的精度损失问题。延伸阅读仓库内相关资源本题属于「排序 自定义比较」类问题与本仓库的以下资源互为补充articles/sort-an-array.md快速排序、归并排序、堆排序的完整多语言实现可用于加深对排序算法稳定性与复杂度的理解articles/sort-colors.md 与 articles/kth-largest-element-in-an-array.md同属数组排序 / 选择类问题的经典变体README.md本仓库共收录 Python、Java、JavaScript、C、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C、Scala、Dart 等 14 种语言的题解本文代码遵循仓库的「Solution 类 单方法」统一签名规范详见 articles/README.md 的编写指南便于直接对照 LeetCode 环境运行验证。动手验证建议将上述任意语言的sortJumbled(mapping, nums)方法直接粘贴到 LeetCode 2191 的编辑器运行重点用以下用例自测mapping [9,8,7,6,5,4,3,2,1,0]nums [0, 1, 2]验证 0 特判与稳定排序构造包含多个映射值相等的数如mapping[0]0时数字0与00类场景验证相对顺序构造接近题目上限的大数验证溢出处理。通过「字符串法」与「算术法」两套实现的对照练习即可把本题沉淀为「映射键 稳定排序」这一类题的通用模板。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考