LC1122.数组的相对排序

• 原题链接：https://leetcode.cn/problems/relative-sort-array/

思路：改变规则的计数排序

• 首先统计arr1中各个元素出现的频率，记在数组rec当中
• 接着，按照arr2中各个元素的出现次序，将该部分元素按照rec数组里面的频率，打印出来，打印之后将频率清零，这样我就知道出现在**arr1**，但是没有出现在**arr2**当中 的所有元素（即频率不为0的元素）。

• 那么，剩下那一部分（在arr1中，但是不在arr2中的元素们），按照升序，将其全部打印出来即可。

  代码：

  class Solution {
  public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int min_num = *min_element(arr1.begin(), arr1.end());
        int max_num = *max_element(arr1.begin(), arr1.end()) - min_num;
        int n1 = arr1.size(), n2 = arr2.size();
        // 计数排序
        vector<int> rec(max_num + 5, 0);
        for (int i = 0; i < n1; i++) {
            rec[arr1[i] - min_num] += 1;
        }
        vector<int> ans;
        for (int i = 0; i < n2; i++) {
            for (int k = 0, nr = rec[arr2[i] - min_num]; k < nr; k++) {
                ans.push_back(arr2[i]);
                rec[arr2[i] - min_num] -= 1;
            }
        }
        for (int i = 0; i <= max_num; i++) {
            while (rec[i] > 0) {
                ans.push_back(i + min_num);
                rec[i] -= 1;
            }
        }
        return ans;
    }
  };