题目描述

给定两个数组 arr1 和 arr2，arr2 的元素互不相同，arr2 中的所有元素都在 arr1 中出现过。

排序 arr1 中的元素使得 arr1 的相对顺序和 arr2 一样。没有出现在 arr2 中的元素应该按照 升序 放在 arr1 的最后。

样例

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

限制

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2[i] 都是不同的。
• arr2[i] 在 arr1 中出现过。

算法

(排序) $O(n \log n)$

1. 将 arr2 中的每个数字记录顺序，然后按照顺序自定义比较函数对 arr1 排序。
2. 在 arr1 中没有被记录过顺序的数字，其顺序为 n + x ，x 为这个数字。

时间复杂度

• 记录顺序时间复杂度为 $O(n)$，排序时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外的 $O(n)$ 的空间记录顺序。

C++ 代码

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int n = arr2.size();
        unordered_map<int, int> order;

        for (int i = 0; i < n; i++)
            order[arr2[i]] = i;

        auto cmp = [&](int x, int y) {
                int ox = n + x, oy = n + y;
                if (order.find(x) != order.end())
                    ox = order[x];
                if (order.find(y) != order.end())
                    oy = order[y];
                return ox < oy;
            };

        sort(arr1.begin(), arr1.end(), cmp);

        return arr1;
    }
};