LeetCode LCR 075. 数组的相对排序

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 075. 数组的相对排序

题意分析

给两个数组 arr1 与 arr2，其中 arr2 的元素互不相同且都出现在 arr1 里。要求重排 arr1：在 arr2 中出现过的元素，按它们在 arr2 中的先后顺序排列；没出现过的元素，统统排在后面并按升序排列。

这是一道「自定义序」的排序题。排序的依据不是元素本身的大小，而是一张外部给定的优先级表。核心工作是把「在 arr2 中的位置」这个信息变成一个可比较的数值键。

「未出现的元素排在最后且内部升序」这句话说明键需要分两层：第一层区分「是否在 arr2 中」以及在其中的名次，第二层在未出现的元素之间按值比较。两层可以合并成一个键，也可以写成两级比较。

arr2 的元素互不相同这一条很关键，它保证了「值 → 名次」是一个单射，可以直接用哈希表存；否则同一个值会有多个名次，语义就不明确了。

约束是两个数组长度都不超过 1000，元素取值范围是 [0, 1000]。取值范围有限且很小，这是一个明显的信号——存在 $O(n + C)$ 的计数排序解法；同时规模又小到 $O(n \log n)$ 的通用排序完全够用。

边界上要注意：arr1 中可以有重复元素，相同的值必须挨在一起且不能丢失个数；arr2 可能覆盖 arr1 的全部元素，此时没有「剩余部分」；也可能 arr1 中有大量不在 arr2 里的元素。

解法：哈希表统计状态

核心思路

暴力做法是按 arr2 的顺序逐个元素扫描 arr1，把等于它的全部取出来放进结果，最后再把剩下的收集起来排序。代价是 $O(m \cdot n + k \log k)$，正确但把「查名次」这件事做成了反复的全数组扫描。

瓶颈在于优先级的查询方向：暴力是拿着 arr2 的每个元素去 arr1 里找所有匹配项，同一段数组被扫了 $m$ 遍。而每个 arr1 元素的名次其实是一次查表就能确定的常量。

观察到：只要能给 arr1 的每个元素算出一个排序键，使得键的自然升序恰好等于题目要求的顺序，那么整个问题就退化成一次普通排序。剩下的全部工作就是设计这个键。

键的设计如下：先用哈希表建立「值 → 在 arr2 中的下标」的映射。对 arr1 中的元素 v——若它在 arr2 中，键取它的下标，范围是 [0, m - 1]；若不在，键取 m + v，范围是 [m, m + 1000]。

这个键同时完成了两件事。第一，未出现元素的键恒不小于 m，而出现元素的键恒小于 m，两组天然分开且顺序正确；第二，未出现元素之间的键是 m + v，随 v 单调递增，按键排序就等于按值升序，第二层比较被免费包含进来了。用一个单调的偏移量把两级比较压成一级，是这个键设计的巧妙之处。

维持的不变量是：排序键的升序与题目要求的目标顺序完全一致。只要这一条成立，用任何排序算法排完再取回原值即可，正确性不依赖排序的稳定性——相同的原值必然拥有相同的键，它们内部谁先谁后不影响结果。

解题步骤

遍历 arr2 建立「值 → 下标」的哈希表。用哈希而不是保留数组做线性查找，是为了把单次名次查询从 $O(m)$ 降到 $O(1)$。

为 arr1 的每个元素构造一个「（原值，排序键）」的配对。之所以要把原值一起带上，是因为排序是按键进行的，排完之后还要能取回元素本身。

键的计算：在哈希表中命中就取下标；未命中则取 arr2.length + 原值。偏移量取 arr2.length 而不是随便一个大数，是为了保证「未出现组的最小键」恰好紧接在「出现组的最大键」之后，两组不重叠也不留下语义空洞。

按键升序排序。由于键已经完整编码了两层规则，比较器只需要一个字段，不必写多级判断。

把排序后的原值依次写回 arr1 并返回。写回原数组可以省掉一次分配，也符合题目「重新排列 arr1」的语义。

以 arr1 = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19]、arr2 = [2, 1, 4, 3, 9, 6] 走一遍：哈希表是 {2:0, 1:1, 4:2, 3:3, 9:4, 6:5}，m = 6。逐个算键：三个 2 都是 0；两个 3 都是 3；1 是 1；4 是 2；6 是 5；9 是 4；7 不在表中，键为 6 + 7 = 13；19 不在表中，键为 6 + 19 = 25。把这些配对按键升序排列，得到键序列 0, 0, 0, 1, 2, 3, 3, 4, 5, 13, 25，对应的原值序列是 2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19。可以逐段核对：键 0 到 5 的部分严格按 arr2 的顺序 2, 1, 4, 3, 9, 6 排列，且每个值的重复次数与 arr1 中一致；键 13 与 25 的部分是不在 arr2 中的 7 与 19，按值升序排在最后。返回 [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]。

代码实现

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][0];
        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;
    }
}

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)$，建哈希表是 $O(m)$、构造键是 $O(n)$，排序占据主导。若改用计数排序可以降到 $O(n + m + C)$，其中 $C = 1001$ 是取值范围。

空间复杂度：$O(m + n)$，哈希表存下 arr2 的全部映射，配对数组与 arr1 等长；返回值复用了原数组因而不额外计费。

关键点总结

自定义顺序的排序题，通用解法是「设计一个排序键，使键的自然序等于目标序」。把规则前置到键里，排序本身就退化成库函数调用，正确性也更容易论证。

多级比较可以压成单键：给低优先级的组加上一个大于高优先级组全部取值的偏移量，再让组内的量单调地叠加上去。这个技巧在「先按类别再按数值」的场景里能反复复用。

偏移量要选「恰好接续」的值（这里是 arr2.length），既保证两组不重叠，也让键的含义可读；随便选一个大常数虽然也能跑对，但一旦取值范围变化就可能撞车。

「元素互不相同」是把值映射成名次的前提。看到需要建立「值 → 属性」的映射时，先确认这个映射确实是单射。

本题的取值范围只有 [0, 1000]，这是计数排序的明确信号：开一个长度 1001 的计数数组，先按 arr2 的顺序输出各值的全部计数，再从小到大输出剩余的值，可以做到 $O(n + m + C)$ 且不需要比较排序。

面试视角：先给出哈希键 + 排序的通用解，再主动指出「取值范围只有 1001，可以用计数排序做到线性」，两条路线一起讲能明显拉开区分度；面试官出这题往往就是想听「值域有限」这四个字。

面试视角：常见追问是「如果值域很大但 arr2 很小怎么办」。答此时计数排序不划算，仍用哈希键 + 比较排序，复杂度 $O(n \log n)$ 与值域无关，这正是两种方案的取舍分界。

易错点总结

错误写法：未出现元素的键直接取原值，不加偏移。用例 arr1 = [2, 1]、arr2 = [2] → 1 的键是 1、2 的键是 0，排出 [2, 1] 虽凑巧正确；但换成 arr1 = [19, 2, 1, 4, 3]、arr2 = [2, 1, 4, 3] 时，19 的键 19 与名次键混在同一值域，若某个名次也达到 19 就会错序，且未出现元素可能被排到中间。

错误写法：偏移量取 arr2.length 但键写成 arr2.length + 下标 之类与原值无关的常量。用例 arr1 = [19, 7, 2]、arr2 = [2] → 未出现的 19 与 7 键相同，内部顺序由排序的稳定性决定，输出 [2, 19, 7]，正确答案是 [2, 7, 19]，第二层升序丢失。

错误写法：比较器写成 a[1] - b[1] 却让键的取值范围跨越正负极值。用例键值达到 $10^9$ 量级 → 相减溢出成负数，排序顺序错乱；本题键值很小不会触发，但同一写法搬到大值域题目上立刻出错，稳妥写法是 Integer.compare(a[1], b[1])。

错误写法：用 arr2 的线性查找 indexOf 代替哈希表。用例 arr1 与 arr2 都是 1000 长 → 每个元素查一次名次要 $O(m)$，总代价 $10^6$ 次比较外加排序，虽勉强能过，但把 $O(1)$ 的查表写成 $O(m)$ 完全失去了哈希的意义。

错误写法：先把 arr1 中出现在 arr2 里的元素去重再排。用例 arr1 = [2, 2, 2, 1]、arr2 = [2, 1] → 输出 [2, 1]，正确答案是 [2, 2, 2, 1]；重复元素必须全部保留。

错误写法：认为剩余元素应保持它们在 arr1 中的原有相对顺序。用例 arr1 = [19, 7, 2]、arr2 = [2] → 输出 [2, 19, 7]，正确答案是 [2, 7, 19]，题目明确要求剩余部分升序。

错误写法：只排序键数组而忘了把原值一起搬运。用例 arr1 = [2, 1]、arr2 = [1, 2] → 排完键之后无法还原对应的元素，写回时张冠李戴，输出与输入无关。

错误写法：把 arr2 里的元素按值升序而不是按给定下标排序。用例 arr1 = [2, 1]、arr2 = [2, 1] → 输出 [1, 2]，正确答案是 [2, 1]；arr2 给的是顺序表而非大小关系。

相似题目

题目	难度	考察点
1122. 数组的相对排序	简单	与本题同题，可用来对照哈希排序键与计数排序两种实现
1365. 有多少小于当前数字的数字	简单	同样利用值域有限做计数，但求的是前缀累计而非重排
1636. 按照频率将数组升序排序	简单	排序键换成频次，且频次相同时要按值降序，是两级比较的直接练习
451. 根据字符出现频率排序	中等	键为字符频次，输出要按频次展开成字符串而非下标重排
179. 最大数	中等	排序键无法用单值表达，必须自定义两两拼接的比较规则
75. 颜色分类	中等	值域只有三个，可用三路划分做到一趟原地排序
922. 按奇偶排序数组 II	简单	顺序约束落在下标奇偶而非元素值，靠双指针原地交换完成