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:
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
- Each
arr2[i]
is distinct. - Each
arr2[i]
is inarr1
.
A:
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { vector<int> res; vector<int> diff; unordered_set<int> S(arr2.begin(), arr2.end()); unordered_map<int,int> Count; for(auto val : arr1){ if(S.find(val) == S.end()){ diff.push_back(val); }else{ Count[val] += 1; } } for(int val : arr2){ for(int i =0;i<Count[val];i++) res.push_back(val); } sort(diff.begin(), diff.end()); res.insert(res.end(), diff.begin(), diff.end()); return res; } };
No comments:
Post a Comment