一、题目

在这里插入图片描述

二、方法一：哈希

没错，，简单题，就是说将arr1中有arr2的元素，则按照arr2的元素先排列（特别注意：这里的arr2的元素都是不同的，但是arr1中是可以元素重复的），然后arr1中不是arr2的元素则被丢到arr1的尾巴。

可以用哈希，用mp1记录arr1数组每种数字的出现次数，mp2记录arr2数组的是否出现，接着就是上面说的逻辑，，就是脑子清醒点，mp1[arr2[i]]这种东西不要搞乱了。

三、代码

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        //mp1记录arr1数组每种数字的出现次数
        map<int, int>mp1;
        //mp2记录arr2数组的是否出现
        map<int, bool>mp2;
        for(int i = 0; i < arr2.size(); i++){
            mp2[arr2[i]] = true;
        }
        //temp装arr1中没有arr2的元素
        vector<int>temp;
        for(int j = 0; j < arr1.size(); j++){
            //arr1中是arr2的数字
            mp1[arr1[j]] += 1;
            if(mp2[arr1[j]] == false){
                temp.push_back(arr1[j]);
            }
        }
        sort(temp.begin(), temp.end());
        vector<int>ans;
        //遍历arr2
        for(int i = 0; i < arr2.size(); i++){
            for(int j = 0; j < mp1[arr2[i]]; j++){
                ans.push_back(arr2[i]);
            }
        }
        for(int i = 0; i < temp.size(); i++){
            ans.push_back(temp[i]);
        }
        return ans;
    }
};

四、法二：自定义排序

记录一种更方便的方法：排序并自定义比较函数。

由于数组 $a r r_{2}$ 规定了比较顺序，因此我们可以使用哈希表对该顺序进行映射：即对于数组 $a r r_{2}$ 中的第 $i$ 个元素，我们将 $\left(\operatorname{arr}_{2}[i], i\right)$ 这一键值对放入哈希表 $\operatorname{rank}$ 中，就可以很方便地对数组 $\operatorname{arr}_{1}$ 中的元素进行比较。

比较函数的写法有很多种，这里最基础的比较方法，对于元素 $x$ 和 $y$ :

如果 $x$ 和 $y$ 都出现在哈希表中，那么比较它们对应的值 $\operatorname{rank}[x]$ 和 $\operatorname{rank}[y]$ ;
如果 $x$ 和 $y$ 都没有出现在哈希表中，那么比较它们本身；
对于剩余的情况，出现在哈希表中的那个元素较小。

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> rank;
        for (int i = 0; i < arr2.size(); ++i) {
            rank[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [&](int x, int y) {
            if (rank.count(x)) {
                return rank.count(y) ? rank[x] < rank[y] : true;
            }
            else {
                return rank.count(y) ? false : x < y;
            }
        });
        return arr1;
    }
};