1. 题目

给你两个数组，arr1 和 arr2，

arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

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

提示：

arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 arr2 中的元素 arr2[i] 各不相同 arr2 中的每个元素 arr2[i] 都出现在 arr1 中

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/relative-sort-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

2.1. 自定义排序

若arr1中元素在arr2中出现过，则增添一个位置信息pos；若未出现过，pos设为最大值。

排序时先按pos排，再按值val排即可

2.2. 计数排序

该题就是一个桶排序，先把arr2中的数按顺序拿完，在把桶中剩下的按顺序拿完

3. 代码

3.1. 自定义排序

class Solution {
public:
    struct node{
        int val;
        int pos;
        node(int v,int p){
            val=v,pos=p;
        }
        bool operator<(const node &n2) const{
            if(pos!=n2.pos) return pos<n2.pos;
            else return val<n2.val;
        }
    };
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<node> Arr;
        unordered_map<int,int> table;
        for(int i=0;i<arr2.size();++i){
            table[arr2[i]]=i;
        }
        for(int i=0;i<arr1.size();++i){
            if(table.count(arr1[i])) Arr.emplace_back(arr1[i],table[arr1[i]]);
            else Arr.emplace_back(arr1[i],arr2.size());
        }
        sort(Arr.begin(),Arr.end());  
        for(int i=0;i<arr1.size();++i)
            arr1[i] = Arr[i].val;
        return arr1;
    }
};

看官方题解时，发现可以写的更简单，比如那个结构体不必显式定义出来

可惜的是时间性能并没有改善，甚至比我上面的代码还慢

官方题解：

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

在sort函数里直接定义排序规则，这种写法我也是第一次在C++里碰见，没找到相关资料，期待后续能学习到。

3.2. 计数排序

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> ans;
        map<int,int> table;
        for(auto &x:arr1) table[x]++;
        for(auto &x:arr2) while(table[x]--) ans.push_back(x);
        for(auto &x:table) while(x.second-->0) ans.push_back(x.first);
        return ans;
    }
};

用map替代unordered_map，是因为map中元素默认排序方法为按first升序