湖北网站设计制作价格链接买卖
Every day a Leetcode
题目来源：1122. 数组的相对排序
解法1：哈希
用集合 set 存储 arr2 中的元素。
遍历数组 arr1 ，设当前元素为 num：
- 如果 num 在 set 中出现，用哈希表 hash 记录 num 和它出现的次数。
- 否则，用将 num 插入数组 remain。
遍历数组 arr2，设当前元素为 num。向 ans 中插入 hash[num] 个 num。
将 remain 增序排序，将 remain 插入 ans 的后面。
代码：
/** @lc app=leetcode.cn id=1122 lang=cpp** [1122] 数组的相对排序*/// @lc code=start
class Solution
{
public:vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2){unordered_map<int, int> hash;set<int> set(arr2.begin(), arr2.end());vector<int> remain;for (const int &num : arr1){if (set.count(num))hash[num]++;elseremain.push_back(num);}vector<int> ans;for (const int &num : arr2){if (hash.count(num))for (int i = 0; i < hash[num]; i++)ans.push_back(num);}// 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾sort(remain.begin(), remain.end());for (int i = 0; i < remain.size(); i++)ans.push_back(remain[i]);return ans;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(mlogm+n)，其中 m 和 n 分别是数组 arr1 和 arr2 的长度。构建哈希表的时间复杂度为 O(n)，排序的时间复杂度为 O(mlogm)。
空间复杂度：O(logm+n)，其中 m 和 n 分别是数组 arr1 和 arr2 的长度。哈希表的空间复杂度为 O(n)，排序使用的栈的空间复杂度为 O(mlogm)。
解法2：计数排序
注意到本题中元素的范围为 [0, 1000]，这个范围不是很大，我们也可以考虑不基于比较的排序，例如「计数排序」。
优化：实际上，我们不需要使用长度为 1001 的数组，而是可以找出数组 arr1 中的最大值 upper，使用长度为 upper+1 的数组即可。
代码：
/** @lc app=leetcode.cn id=1122 lang=cpp** [1122] 数组的相对排序*/// @lc code=start
// class Solution
// {
// public:
// vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2)
// {
// unordered_map<int, int> hash;
// set<int> set(arr2.begin(), arr2.end());
// vector<int> remain;
// for (const int &num : arr1)
// {
// if (set.count(num))
// hash[num]++;
// else
// remain.push_back(num);
// }
// vector<int> ans;
// for (const int &num : arr2)
// {
// if (hash.count(num))
// for (int i = 0; i < hash[num]; i++)
// ans.push_back(num);
// }
// // 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾
// sort(remain.begin(), remain.end());
// for (int i = 0; i < remain.size(); i++)
// ans.push_back(remain[i]);
// return ans;
// }
// };class Solution
{
public:vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2){int upper = *max_element(arr1.begin(), arr1.end());vector<int> freq(upper + 1, 0);for (const int &num : arr1)freq[num]++;vector<int> ans;for (const int &num : arr2){for (int i = 0; i < freq[num]; i++)ans.push_back(num);freq[num] = 0;}for (int num = 0; num <= upper; num++)for (int i = 0; i < freq[num]; i++)ans.push_back(num);return ans;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(m+n+upper)，其中 m 和 n 分别是数组 arr1 和 arr2 的长度。upper 是数组 arr1 的最大值。
空间复杂度：O(upper)，其中 upper 是数组 arr1 的最大值。即为数组 freq 需要使用的空间。