题目描述
思路解析动画文字版
记牢三步:填桶、按 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 之外的值。
参考代码
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))复杂度
- 时间：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) 的桶
易错点
面试追问把动画讲成自己的话
追问为什么这题能用计数排序,而不是非得用通用比较排序?
追问三种语言怎么保证缺席的值排在末尾还按升序?
追问arr2 里的元素一定都在 arr1 里吗,反过来呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分割平衡字符串
LeetCode 1221 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题