Easy
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
.
题目大意:给出两个数组arr1和arr2,arr2中存在的元素必存在于arr1中,将arr1中的元素按照其在arr2的顺序进行排列,不在arr2中的元素按升序排列在数组末尾。
方法:
由于arr1中的元素可能存在重复,那么排列的时候就要将他们聚在一起。因此可选用一个容器收纳arr1中的元素并记录他们的个数,然后再按照arr2中元素的出现顺序得到结果。
因为不在arr2中的元素要按升序排列,所以使用排序的map容器收纳arr1中元素。
代码如下:
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { vector<int> res; map<int,int> nums; for(int n:arr1){ nums[n]+=1; } for(int m:arr2){ for(int i=0;i<nums[m];++i){ res.push_back(m); } nums.erase(m); } for(auto k:nums){ for(int i=0;i<k.second;++i){ res.push_back(k.first); } } return res; } };