###### 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:

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());

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;
    }
};