§1

题目描述

给定 arr1 和 arr2,arr2 中元素各不相同且都出现在 arr1 中。重排 arr1,使得在 arr2 里出现过的元素,相对顺序与 arr2 一致;没在 arr2 出现过的元素,按升序放在 arr1 的末尾。

输入 = arr1=[2,3,1,3,2,4,6,7], arr2=[2,1,4,3]　输出 = [2,2,1,4,3,3,6,7]

输入 = arr1=[28,6,22,8,44,17], arr2=[22,28,8,6]　输出 = [22,28,8,6,17,44]

§2

思路解析

一句话答案：LeetCode 1122 数组的相对排序：给每个数配一把排序钥匙——在 arr2 里的按出现位置排、缺席的用 1000 加自身值压到末尾还自带升序，一次 sorted 排完，时间 O(n log n)。

arr1 按 arr2 的顺序重排，缺席的数放哪

给两个数组 arr1、arr2，arr2 里的数互不相同、且都在 arr1 里出现过。重排 arr1：在 arr2 出现过的数，相对顺序照 arr2 排；没出现过的，按从小到大接在末尾。题面例子 arr1=[2,3,1,3,2,4,6,7]、arr2=[2,1,4,3]，输出 [2,2,1,4,3,3,6,7]——前半段跟着 arr2 的 2、1、4、3 走，末尾 6、7 没在 arr2 里，按升序补上。

arr2 的顺序不是数值大小，排序键怎么写

别扭在两段用两套规则。arr2 段照 arr2 的先后走，可 arr2=[2,1,4,3] 里 1 反排在 2 后头，压根不是按数值；缺席段又得按数值从小到大。真写一个两两比较的比较器，就得分三种情况掰扯：两个数都在 arr2、只有一个在、两个都不在，判法各异，写着就漏掉一支。

给每个数配一把排序钥匙

不两两比较，而是给每个数单独算一把排序钥匙，再让所有数照钥匙升序排。在 arr2 里出现的数，钥匙就是它在 arr2 里的下标：2 在第 0 位记 0，1 在第 1 位记 1，照钥匙排自然还原了 arr2 的先后。

缺席的数没下标，给它 1000 加自身的值当钥匙。1000 这个大偏移比 arr2 里任何下标都大，把缺席的数整批压到 arr2 段后面；再叠上自身值，缺席的数彼此按数值分了高下，升序跟着成立。

一张位置表配一次 sorted

落到代码：先扫一遍 arr2 建位置表 pos，把每个值映射到下标，pos={2:0, 1:1, 4:2, 3:3}。排序时按 x 取钥匙：x 在 pos 里用 pos[x]，不在用 1000+x——Python 一句 pos.get(x, 1000+x) 把两种情况都兜住。最后 sorted(arr1, key=…) 照钥匙排一遍返回，不用自己拆两段再拼。

[2,3,1,3,2,4,6,7] 每个数的钥匙是多少

先建 pos={2:0, 1:1, 4:2, 3:3}。逐个取钥匙：两个 2 都拿 0，两个 3 都拿 3，1 拿 1，4 拿 2；6、7 没进 pos，分别拿 1000+6=1006、1000+7=1007。

按钥匙升序排：钥匙 0 的两个 2 打头，接钥匙 1 的 1、钥匙 2 的 4、钥匙 3 的两个 3，排成 2、2、1、4、3、3；钥匙 1006、1007 的 6、7 压最后，拼起来就是题面输出 [2,2,1,4,3,3,6,7]，一个不差。

复杂度，以及偏移取小了会怎样

扫 arr2 建位置表是 O(m)，m 是 arr2 长度；耗时大头是给 arr1 排的那一遍，O(n log n)，n 是 arr1 长度。空间上位置表占 O(m)、排序内部还要 O(n)，合起来 O(n)。

偏移那个 1000 别图省事改小：本题值和下标都不超过 1000，偏移一旦比某个下标还小，缺席的数会插进 arr2 段里、顺序全错；两段规则也别搅一起排，arr2 段照下标、缺席段照数值；C++ 里只比下标不比值，缺席值下标全相同，彼此升序会没着落，得靠 pair 第二维的值兜底。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

记牢三步:填桶、按 arr2 倒桶、剩下的桶按值升序补尾。下面每一帧都在套这三步。

阶段一 · 准备填桶：右边这排是计数桶,每个桶对应一个值,从 1 到 7 排好,现在全是 0。下面从左到右扫 arr1,看到一个数就给它的桶加 1。

填桶 · 第 0 个数 2：扫到 arr1[0] = 2,把 2 的桶加 1,现在桶[2] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 1 个数 3：扫到 arr1[1] = 3,把 3 的桶加 1,现在桶[3] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 2 个数 1：扫到 arr1[2] = 1,把 1 的桶加 1,现在桶[1] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 3 个数 3：扫到 arr1[3] = 3,把 3 的桶加 1,现在桶[3] = 2。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 4 个数 2：扫到 arr1[4] = 2,把 2 的桶加 1,现在桶[2] = 2。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 5 个数 4：扫到 arr1[5] = 4,把 4 的桶加 1,现在桶[4] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 6 个数 6：扫到 arr1[6] = 6,把 6 的桶加 1,现在桶[6] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。

填桶 · 第 7 个数 7：扫到 arr1[7] = 7,把 7 的桶加 1,现在桶[7] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。

阶段一完成 · 桶都填好了：8 个数全填完了。注意值 5 没出现过,桶[5] 还是 0,等会儿升序补尾时会自然跳过它。接下来开始倒桶。

阶段二 · 按 arr2 倒桶：现在看 arr2 = [2,1,4,3]。它就是一把「顺序尺」:arr2 里第一个是 2,就先把桶[2] 里的数全倒出来,再轮到下一个。

倒桶 · arr2 第 0 位 2：arr2 第 0 位是 2,桶里原来有 2 个 2。倒出第 1 个,接到输出后面,桶[2] 剩 1 个。

倒桶 · arr2 第 0 位 2：arr2 第 0 位是 2,桶里原来有 2 个 2。倒出第 2 个,接到输出后面,桶[2] 剩 0 个。

倒桶 · arr2 第 1 位 1：arr2 第 1 位是 1,桶里就 1 个 1。倒出来接到输出后面,桶[1] 清空成 0。

倒桶 · arr2 第 2 位 4：arr2 第 2 位是 4,桶里就 1 个 4。倒出来接到输出后面,桶[4] 清空成 0。

倒桶 · arr2 第 3 位 3：arr2 第 3 位是 3,桶里原来有 2 个 3。倒出第 1 个,接到输出后面,桶[3] 剩 1 个。

倒桶 · arr2 第 3 位 3：arr2 第 3 位是 3,桶里原来有 2 个 3。倒出第 2 个,接到输出后面,桶[3] 剩 0 个。

阶段三 · 剩余桶升序补尾：arr2 里的值都倒完了。现在从小到大扫一遍桶,还有数的是 6 和 7。桶[5] 是空的,直接跳过。把剩下的按值升序补到输出末尾。

补尾 · 值 6：6 没在 arr2 里出现过,轮到它按升序补尾。倒出一个 6 接到末尾,输出现在是 [2,2,1,4,3,3,6]。

补尾 · 值 7：7 没在 arr2 里出现过,轮到它按升序补尾。倒出一个 7 接到末尾,输出现在是 [2,2,1,4,3,3,6,7]。

完成 · 答案 [2,2,1,4,3,3,6,7]：桶全倒空了。前半段 2、2、1、4、3、3 严格跟着 arr2 的 2、1、4、3,后半段 6、7 是缺席的数按升序补的。最终答案 [2,2,1,4,3,3,6,7] 成立。

边界先想清:全员在 arr2(无尾段)、含 0 的缺席值升序、重复值成块连排。

面试重点:值域小所以能用桶、三语言用排序键把缺席值压到末尾、arr1 可以有 arr2 之外的值。

§3

参考代码

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution:    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:        pos = {x: i for i, x in enumerate(arr2)}        return sorted(arr1, key=lambda x: pos.get(x, 1000 + x))

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n log n)，n 为 arr1 长度。参考代码主要花在排序 O(n log n);建位置表扫 arr2 是 O(m)。动画的计数桶法是 O(n + k),k 为值域(本题 0 到 1000)
空间：O(n)，存「键值对/排名值对」数组 O(n) 加位置表 O(m)。排序内部:C++ 排序额外栈约 O(log n),Java 对象数组排序(TimSort)与 Python 的 sort 都可能用 O(n) 额外空间。计数桶法则是 O(k) 的桶

§5

易错点

✗ 错误写法：把没在 arr2 出现的数也塞进 arr2 那段乱排

✓ 正确写法：缺席的值单独按值升序放末尾

题目对两段规则不同:arr2 段跟 arr2 顺序,缺席段按值升序,不能混为一谈

✗ 错误写法：Python 的偏移 1000 改成一个很小的数

✓ 正确写法：偏移必须比 arr2 里所有排名都大

排名是 0 到 arr2 长度减 1,偏移太小会让缺席值插进 arr2 段里、顺序就错了

✗ 错误写法：C++ 里只比较排名、不比较值

✓ 正确写法：缺席值排名相同,要靠 pair 第二维的值兜底升序

所有缺席值排名都等于 arr2 长度,光比排名它们之间是乱的,必须再按值升序

面试追问把动画讲成自己的话

追问为什么这题能用计数排序,而不是非得用通用比较排序?

因为题目限定值的范围很小,arr1 和 arr2 里的数都在 0 到 1000 之间。值域有限就可以开一排桶按值计数,填桶 O(n)、按顺序倒桶 O(n + k),整体 O(n + k) 比通用比较排序的 O(n log n) 还快。值域很大或是浮点数时,才退回到自定义比较器加排序的写法。

追问三种语言怎么保证缺席的值排在末尾还按升序?

核心都是给缺席值一个「足够靠后、又能体现值大小」的排序键。Python 用 1000 加自身当键,Java 用 arr2 长度加自身当键,这两种都把值本身编进了键里,自然升序;C++ 给所有缺席值同一个排名 arr2 长度,再靠 pair 排序先比排名、相同再比第二维的值,达到同样效果。

追问arr2 里的元素一定都在 arr1 里吗,反过来呢?

arr2 的每个元素题目保证都在 arr1 里出现过,所以倒桶时不会扑空。但反过来不成立:arr1 里可以有 arr2 没有的值,这些就是要走末尾升序补尾的那批。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 贪心套路 6/62

分割平衡字符串

LeetCode 1221 · 简单 · 沿着贪心套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: pos = {x: i for i, x in enumerate(arr2)} return sorted(arr1, key=lambda x: pos.get(x, 1000 + x))