将杂乱无章的数字排序
难度:
标签:
题目描述
代码结果
运行时间: 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 中,为什么首先需要将数字转换成字符串才能应用映射?
▷🦆
映射表 mp 是如何确保每个数位正确映射到其对应的新数字的?
▷🦆
解题思路中提到的 '转换后的结果' 是指的什么?它是如何影响排序的?
▷🦆
sorted 函数是如何保证那些映射后相等的数字保持输入中的相对顺序的?
▷