---
# System prepended metadata

title: 1122. Relative Sort Array
tags: [counting, Leetcode, python, array, c++, sort, easy]

---

###### tags: `Leetcode` `easy` `array` `counting` `sort` `python` `c++`

# 1122. Relative Sort Array

## [題目連結:] https://leetcode.com/problems/relative-sort-array/description/

## 題目:
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 do not 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]
```
**Example 2:**
```
Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]
```

## 解題想法:
* 此題為，給兩個數組:
    * arr1: 很長，可能有重複數字
    * arr2: 精簡，不重複，所有元素皆有出現在arr1
    * 將arr1的元素順序，排序成arr2中元素的順序
        * 其中arr1裡面未出現於arr2的數字，移至最尾且由小到大排序

* 想法:
    * 初始所需參數
        * appear=set(arr2)
        * res=[]
        * tmp=[]
        * dic=defaultdict(int)
    * Step1:用dic字典存arr1:
        * key: 當前數字
        * val: 出現次數
    * Step2:
        * 用res存每個arr2中的數字* dic[數字]
    * Step3:
        * 將arr1中尚未出現在arr2的數字
        * 存於tmp
    * Step4:
        * tmp.sort()
    * Step5:
        * res+tmp

## Python:
``` python=
from collections import defaultdict
class Solution(object):
    def relativeSortArray(self, arr1, arr2):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: List[int]
        """
        appear=set(arr2)
        res=[]
        tmp=[]
        dic=defaultdict(int)
        #collect num of the val
        for val in arr1:
            dic[val]+=1
        #add to res
        for val in arr2:
            res+=[val]*(dic[val])
        #add val which didnt in arr2 to tmp
        for val in arr1:
            if val not in appear:
                tmp.append(val)
        tmp.sort()
        return res+tmp
```

## C++:
* 初始化set: (array.begin(), array.end());
``` cpp=
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int,int> dic;
        vector<int> res,tmp;
        set<int> appear(arr2.begin(), arr2.end());
        for (int val: arr1){
            dic[val]+=1;
        }
        for (int val: arr2){
            for (int i=0; i<dic[val]; i++) res.push_back(val);
        }
        for (int val: arr1){
            if (appear.find(val)==appear.end())
                tmp.push_back(val);
        }
        sort(tmp.begin(), tmp.end());
        for (int val: tmp){
            res.push_back(val);
        }
        return res;
    }
};
```