# 1122. Relative Sort Array

Given two arrays `arr1` and `arr2`, the elements of `arr2` are distinct, and all elements in `arr2` are also in `arr1`.

Sort the elements of `arr1` such that the relative ordering of items in `arr1` are the same as in `arr2`.  Elements that don’t appear in `arr2` should be placed at the end of `arr1` in ascending order.

Example 1:

``````Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
``````

Constraints:

• `1 <= arr1.length, arr2.length <= 1000`
• `0 <= arr1[i], arr2[i] <= 1000`
• All the elements of `arr2` are distinct.
• Each `arr2[i]` is in `arr1`.

``````class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> res;
map<int, int> m;
for (int num : arr1) ++m[num];
for (int num : arr2) {
for (int i = 0; i < m[num]; ++i) {
res.push_back(num);
}
m.erase(num);
}
for (auto a : m) {
for (int i = 0; i < a.second; ++i) {
res.push_back(a.first);
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1122

https://leetcode.com/problems/relative-sort-array/

https://leetcode.com/problems/relative-sort-array/discuss/335056/Java-in-place-solution-using-counting-sort

https://leetcode.com/problems/relative-sort-array/discuss/334585/Python-Straight-Forward-1-line-and-2-lines

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation