一、题目
二、方法一：哈希
没错，，简单题，就是说将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}arr
2
规定了比较顺序，因此我们可以使用哈希表对该顺序进行映射：即对于数组 a r r 2 a r r_{2}arr
2
中的第 i ii 个 元素，我们将 ( arr 2 [ i ] , i ) \left(\operatorname{arr}_{2}[i], i\right)(arr
2
[i],i) 这一键值对放入哈希表 rank \operatorname{rank}rank 中，就可以很方便地对数组 arr 1 \operatorname{arr}_{1}arr
1
中的元素进行比较。
比较函数的写法有很多种，这里最基础的比较方法，对于元素 x xx 和 y yy :
如果 x xx 和 y yy 都出现在哈希表中，那么比较它们对应的值 rank [ x ] \operatorname{rank}[x]rank[x] 和 rank [ y ] \operatorname{rank}[y]rank[y];
如果 x xx 和 y yy 都没有出现在哈希表中，那么比较它们本身；
对于剩余的情况，出现在哈希表中的那个元素较小。
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; } };
