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:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• Each arr2[i] is distinct.
• Each arr2[i] is in arr1.

---

題目翻譯:

讓 arr1 的排列類似於 arr2。但如果 arr1 的元素沒在 arr2 之中，則放到最後麵，以遞升來排序。

程式思路:

我們可以利用壓縮的概念來做，先算出 arr2 的元素在 arr1 用了幾個，在一口氣解壓縮，串上 others 的元素，代碼如下。

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> result;
        vector<int> others;
        vector<int> frq (arr2.size(),0);
        int i,j;
        for(i = 0;i < arr1.size();i++){
            for(j = 0;j < arr2.size();j++){
                if(arr1[i]==arr2[j]){
                    //compression
                    frq[j]++;
                    arr1[i] = -1;
                    break;
                }
            }
            if(arr1[i]>=0)
                others.push_back(arr1[i]);
        }
        //uncompression
        for(j = 0;j<arr2.size();j++){
            for(i =0;i<frq[j];i++)
                result.push_back(arr2[j]);
        }
        std::sort(others.begin(), others.end(), std::less<int>());
        for(auto it : others)
            result.push_back(it);

        return result;
    }
};