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:

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
All the elements of arr2 are distinct.
Each arr2[i] is in arr1.

这题给定一个arr2数组，它制定了某些数字的顺序并且唯一，并且都会出现在arr1数组之中。对arr1进行排序，按照arr2的排序，假如不在的，则按正常的大小进行排序。

这里只要按照上述的描述，写一个comparator就行了。

class RelativeSortArray : public Solution {
public:
    void Exec() {

    }
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> dist_orders;
        for (int i = 0; i < arr2.size(); i++) {
            dist_orders[arr2[i]] = i;
        }

        std::sort(arr1.begin(), arr1.end(), [&dist_orders](int a, int b) -> bool {
            auto ai = dist_orders.find(a);
            auto bi = dist_orders.find(b);

            if (ai == dist_orders.end() && bi == dist_orders.end()) {
                return a < b;
            }
            if (ai == dist_orders.end()) {
                return false;
            }
            if (bi == dist_orders.end()) {
                return true;
            }
            return ai->second < bi->second;
        });

        return arr1;
    }
};