leetcode
leetcode 1151 ~ 1200
将杂乱无章的数字排序

将杂乱无章的数字排序

难度:

标签:

题目描述

代码结果

运行时间: 251 ms, 内存: 21.8 MB


/**
 * 思路:
 * 1. 使用Java Stream API处理数据。
 * 2. 定义一个辅助函数将数字映射为新的值。
 * 3. 利用流的sorted方法按照映射后的值排序,保持相对顺序。
 */
import java.util.stream.IntStream;

public class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        return IntStream.range(0, nums.length)
                .boxed()
                .sorted((i, j) -> Integer.compare(getMappedValue(mapping, nums[i]), getMappedValue(mapping, nums[j])))
                .mapToInt(i -> nums[i])
                .toArray();
    }

    // 将数字映射为新的值
    private int getMappedValue(int[] mapping, int num) {
        StringBuilder sb = new StringBuilder();
        for (char c : String.valueOf(num).toCharArray()) {
            sb.append(mapping[c - '0']);
        }
        return Integer.parseInt(sb.toString());
    }
}

解释

方法:

这个解决方案通过创建一个数字映射表,将每个数字字符('0'-'9')映射到对应的新数字字符。这是通过使用 Python 的 str.maketrans 和 map 函数来实现的,生成一个转化表 mp。然后,使用 sorted 函数对 nums 数组进行排序,但排序的依据不是数字本身,而是每个数字转换后的结果。转换是通过将每个数字转为字符串,然后使用 translate 方法应用映射,最后转换回整数来比较。由于 Python 的 sorted 函数稳定(保持相等元素的相对顺序),因此如果两个数字映射后相等,它们会按照在原数组中的顺序排列。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
在函数 sortJumbled 中,为什么首先需要将数字转换成字符串才能应用映射?
在函数 sortJumbled 中,数字首先需要转换成字符串,是因为 str.maketrans 和 translate 方法都是针对字符串操作的。数字本身不能直接被这些方法处理。通过将数字转换为字符串,我们可以对每个数位字符应用映射表,将其转换成对应的新数字字符。
🦆
映射表 mp 是如何确保每个数位正确映射到其对应的新数字的?
映射表 mp 是通过 str.maketrans 方法创建的,该方法接收两个字符串:一个是原始字符集,另一个是目标字符集。在这种情况下,原始字符集是 '0123456789',目标字符集是通过将 mapping 列表中的数字转换为字符串并连接起来生成的。这种对应关系确保每个数字字符 '0' 到 '9' 被正确地映射到它们在mapping列表中的对应数字。
🦆
解题思路中提到的 '转换后的结果' 是指的什么?它是如何影响排序的?
在解题思路中提到的 '转换后的结果' 指的是每个数字在转换成字符串并且通过映射表 mp 处理后形成的新的数字字符串。这个新的数字字符串代表的整数,就是原始数字在映射表下的表示。排序函数 sorted 根据这个 '转换后的结果'(即映射后的整数值)来排序整个列表。这意味着数字的排序依据是它们映射后的数值,而不是原始数值。
🦆
sorted 函数是如何保证那些映射后相等的数字保持输入中的相对顺序的?
sorted 函数是一个稳定的排序算法。这意味着如果两个元素在比较时被认为是相等的,它们会保持在原数组中的相对顺序不变。在 sortJumbled 函数中,如果两个数字映射后的结果相同,sorted 函数会保持它们在输入列表 nums 中的原始顺序,这是稳定排序的一个重要特性。

相关问题