LeetCode LCR 075. 数组的相对排序
题目描述
题意分析
按
arr2指定的先后顺序重排arr1：在arr2中出现的值放在前面，每个值的全部重复项都保留；没有出现在arr2中的值放在后面，并按数值升序排列。
arr2中的值互不相同，所以每个值只有一个确定的优先名次。先把“值对应哪个名次”存入哈希表，再把题目的两层顺序转换成可比较的键，就能调用普通排序完成重排。
解法：按给定名次构造排序键
核心思路
[!blue]
设
m = arr2.length，建立pos[value]表示这个值在arr2中的下标。已指定的优先名次是0..m-1，未指定元素需要排在这些名次之后，再按原值比较。Java 使用一个数值键。已指定元素的键为
pos[value]，未指定元素的键为m+value。这一写法依赖本篇原文给出的非负值域：未指定元素的键至少为m，不会与前面的优先名次混在一起；它们的键又随原值增大，因此后半部分自然升序。配对数组保存的是[原值,键]，按第二项排序，再取回第一项。Go 使用两项组成的键：已指定元素保存
[名次,原值]，未指定元素保存[m,原值]。先比较第一项，第一项相同再比较原值。已指定元素按名次分组，所有未指定元素共享最后一个名次，并在这一组内按值升序。这与 Java 的单键写法达到相同顺序，但字段含义不同。对任意两个不同值，以上键的比较结果都与题目要求一致；同一个值的重复项拥有相同键，排序只移动位置，不丢失次数。因此排完键后取出原值，就得到所需结果，正确性不依赖排序是否稳定。
代码将排序后的值写回
arr1。哈希表只用于查名次，不能把arr1转成集合；重复值必须继续作为多个独立元素保存在配对数组中。
解题步骤
- 遍历
arr2，建立值到名次的映射。- 遍历
arr1，为每次元素出现建立携带原值的排序键。- Java 按配对第二项排序；Go 按第一项、第二项依次比较。
- 从排序后的配对中取出原值，写回
arr1并返回。Go 查询哈希表时用
p, ok := pos[x]区分“未指定”与合法名次零。若arr2覆盖全部值，未指定组为空；否则该组统一放在所有指定元素后面。
代码实现
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
Map<Integer, Integer> pos = new HashMap<>(arr2.length);
for (int i = 0; i < arr2.length; ++i) {
pos.put(arr2[i], i);
}
int[][] arr = new int[arr1.length][];
for (int i = 0; i < arr.length; ++i) {
arr[i] = new int[] {
arr1[i],
pos.getOrDefault(arr1[i], arr2.length + arr1[i])
};
}
Arrays.sort(arr, (a, b) -> a[1] - b[1]);
for (int i = 0; i < arr.length; ++i) {
arr1[i] = arr[i][0];
}
return arr1;
}
}
import (
"sort"
)
func relativeSortArray(arr1 []int, arr2 []int) []int {
pos := map[int]int{}
for i, x := range arr2 {
pos[x] = i
}
arr := make([][2]int, len(arr1))
for i, x := range arr1 {
if p, ok := pos[x]; ok {
arr[i] = [2]int{
p,
x,
}
} else {
arr[i] = [2]int{
len(arr2),
x,
}
}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][0] < arr[j][0] || arr[i][0] == arr[j][0] && arr[i][1] < arr[j][1]
})
for i, x := range arr {
arr1[i] = x[1]
}
return arr1
}
复杂度分析
- 时间复杂度：$O(m+n\log(n+1))$，其中 $m,n$ 分别为两个数组的长度。建立名次和配对是线性工作，排序占主要开销。
- 空间复杂度：$O(m+n)$，分别保存名次映射和配对数组，返回值复用
arr1。
关键点总结
[!green]
- 自定义顺序先由名次划分优先组，未指定值只在最后一组按数值排序。
- Java 单键利用非负值域分开两组；Go 双键直接保存组别和原值，不要把两份代码的字段顺序混淆。
- 键决定位置，原值决定返回内容，二者必须一起移动。
易错点总结
[!yellow]
- 把
arr2自身按数值排序，会破坏它给定的优先顺序。- 把哈希表查询结果零当作“不存在”，会丢掉
arr2中第一个值的优先级。- 对
arr1去重，会丢掉应当保留的重复项。- 将 Java 的
m+value写法直接用于任意负数值域，可能让未指定值混入优先名次；本实现按原文的非负范围构造键。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 791. 自定义字符串排序 | 中等 | 同样由外部序列规定一部分元素的排序优先级，本题对象是整数而不是字符。 |