题目描述
给你两个数组，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 中
题目链接： https://leetcode-cn.com/problems/relative-sort-array/
思路
使用哈希表map<int, int> hash统计 arr1 中每个元素的个数，这里要用 map，不能用 unordered_map，因为 map 默认是按照 key 升序来排列的，我们可以利用这个性质将 arr1 中未出现在 arr2 中的元素按照升序放在 arr1 的末尾。步骤如下：
- 遍历 arr2:
- 当前元素为 arr2[i]，则根据哈希表得到 arr2[i] 在 arr1 中出现的次数 hash[arr2[i]]，然后将 hash[arr2[i]] 个元素放进答案中；
- 将 key 为 arr2[i] 的键值对从 hash 中删除；
- 如果 hash 不为空，说明 arr1 中有多余元素，因为 map 是按照 key 升序排列的，所以遍历 hash，将当前元素的 key 放进答案中。
代码如下：
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
map<int, int> hash;
for(int i=0; i<arr1.size(); i++){
hash[arr1[i]]++;
}
int n = arr1.size();
vector<int> ans;
for(int i=0; i<arr2.size(); i++){
while(hash[arr2[i]]>0){
ans.push_back(arr2[i]);
hash[arr2[i]]--;
}
if(hash.count(arr2[i])==0) hash.erase(arr2[i]);
}
if(!hash.empty()){
for(auto it=hash.begin(); it!=hash.end(); it++){
while(it->second>0){
ans.push_back(it->first);
it->second--;
}
}
}
return ans;
}
};