数组的相对排序 图解题解

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 第二维的值兜底。

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;
    }
}