数组的相对排序 图解题解
这道题到底在问什么
- 输入
- 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]
最优解：一步一步想明白
- 3记牢三步:填桶、按 arr2 倒桶、剩下的桶按值升序补尾。下面每一帧都在套这三步。
- 4右边这排是计数桶,每个桶对应一个值,从 1 到 7 排好,现在全是 0。下面从左到右扫 arr1,看到一个数就给它的桶加 1。
- 5扫到 arr1[0] = 2,把 2 的桶加 1,现在桶[2] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 6扫到 arr1[1] = 3,把 3 的桶加 1,现在桶[3] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 7扫到 arr1[2] = 1,把 1 的桶加 1,现在桶[1] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 8扫到 arr1[3] = 3,把 3 的桶加 1,现在桶[3] = 2。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 9扫到 arr1[4] = 2,把 2 的桶加 1,现在桶[2] = 2。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 10扫到 arr1[5] = 4,把 4 的桶加 1,现在桶[4] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 11扫到 arr1[6] = 6,把 6 的桶加 1,现在桶[6] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 12扫到 arr1[7] = 7,把 7 的桶加 1,现在桶[7] = 1。计数桶记的就是「每个值在 arr1 里出现了几次」。
- 138 个数全填完了。注意值 5 没出现过,桶[5] 还是 0,等会儿升序补尾时会自然跳过它。接下来开始倒桶。
- 14现在看 arr2 = [2,1,4,3]。它就是一把「顺序尺」:arr2 里第一个是 2,就先把桶[2] 里的数全倒出来,再轮到下一个。
- 15arr2 第 0 位是 2,桶里原来有 2 个 2。倒出第 1 个,接到输出后面,桶[2] 剩 1 个。
- 16arr2 第 0 位是 2,桶里原来有 2 个 2。倒出第 2 个,接到输出后面,桶[2] 剩 0 个。
- 17arr2 第 1 位是 1,桶里就 1 个 1。倒出来接到输出后面,桶[1] 清空成 0。
- 18arr2 第 2 位是 4,桶里就 1 个 4。倒出来接到输出后面,桶[4] 清空成 0。
- 19arr2 第 3 位是 3,桶里原来有 2 个 3。倒出第 1 个,接到输出后面,桶[3] 剩 1 个。
- 20arr2 第 3 位是 3,桶里原来有 2 个 3。倒出第 2 个,接到输出后面,桶[3] 剩 0 个。
- 21arr2 里的值都倒完了。现在从小到大扫一遍桶,还有数的是 6 和 7。桶[5] 是空的,直接跳过。把剩下的按值升序补到输出末尾。
- 226 没在 arr2 里出现过,轮到它按升序补尾。倒出一个 6 接到末尾,输出现在是 [2,2,1,4,3,3,6]。
- 237 没在 arr2 里出现过,轮到它按升序补尾。倒出一个 7 接到末尾,输出现在是 [2,2,1,4,3,3,6,7]。
- 24桶全倒空了。前半段 2、2、1、4、3、3 严格跟着 arr2 的 2、1、4、3,后半段 6、7 是缺席的数按升序补的。最终答案 [2,2,1,4,3,3,6,7] 成立。
⚠️ 容易写错的地方
✗ 错：把没在 arr2 出现的数也塞进 arr2 那段乱排
✓ 对：缺席的值单独按值升序放末尾
题目对两段规则不同:arr2 段跟 arr2 顺序,缺席段按值升序,不能混为一谈
✗ 错：Python 的偏移 1000 改成一个很小的数
✓ 对：偏移必须比 arr2 里所有排名都大
排名是 0 到 arr2 长度减 1,偏移太小会让缺席值插进 arr2 段里、顺序就错了
✗ 错：C++ 里只比较排名、不比较值
✓ 对：缺席值排名相同,要靠 pair 第二维的值兜底升序
所有缺席值排名都等于 arr2 长度,光比排名它们之间是乱的,必须再按值升序
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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))C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> pos;
for (int i = 0; i < arr2.size(); ++i) {
pos[arr2[i]] = i;
}
vector<pair<int, int>> arr;
for (int i = 0; i < arr1.size(); ++i) {
int j = pos.count(arr1[i]) ? pos[arr1[i]] : arr2.size();
arr.emplace_back(j, arr1[i]);
}
sort(arr.begin(), arr.end());
for (int i = 0; i < arr1.size(); ++i) {
arr1[i] = arr[i].second;
}
return arr1;
}
};Java
import java.util.*;
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;
}
}复杂度
时间
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) 的桶
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组的相对排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这题能用计数排序,而不是非得用通用比较排序?+
因为题目限定值的范围很小,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 没有的值,这些就是要走末尾升序补尾的那批。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组的相对排序 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。