郑州网站建设tpywlkj,学校网站在哪里找,旺店通app手机企业版下载,在网站上如何做天气预报栏Every day a Leetcode
题目来源#xff1a;1122. 数组的相对排序
解法1#xff1a;哈希
用集合 set 存储 arr2 中的元素。
遍历数组 arr1 #xff0c;设当前元素为 num#xff1a;
如果 num 在 set 中出现#xff0c;用哈希表 hash 记录 num 和它出现的次数。否则1122. 数组的相对排序
解法1哈希
用集合 set 存储 arr2 中的元素。
遍历数组 arr1 设当前元素为 num
如果 num 在 set 中出现用哈希表 hash 记录 num 和它出现的次数。否则用将 num 插入数组 remain。
遍历数组 arr2设当前元素为 num。向 ans 中插入 hash[num] 个 num。
将 remain 增序排序将 remain 插入 ans 的后面。
代码
/** lc appleetcode.cn id1122 langcpp** [1122] 数组的相对排序*/// lc codestart
class Solution
{
public:vectorint relativeSortArray(vectorint arr1, vectorint arr2){unordered_mapint, int hash;setint set(arr2.begin(), arr2.end());vectorint remain;for (const int num : arr1){if (set.count(num))hash[num];elseremain.push_back(num);}vectorint 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 codeend结果 复杂度分析
时间复杂度O(mlogmn)其中 m 和 n 分别是数组 arr1 和 arr2 的长度。构建哈希表的时间复杂度为 O(n)排序的时间复杂度为 O(mlogm)。
空间复杂度O(logmn)其中 m 和 n 分别是数组 arr1 和 arr2 的长度。哈希表的空间复杂度为 O(n)排序使用的栈的空间复杂度为 O(mlogm)。
解法2计数排序
注意到本题中元素的范围为 [0, 1000]这个范围不是很大我们也可以考虑不基于比较的排序例如「计数排序」。
优化实际上我们不需要使用长度为 1001 的数组而是可以找出数组 arr1 中的最大值 upper使用长度为 upper1 的数组即可。
代码
/** lc appleetcode.cn id1122 langcpp** [1122] 数组的相对排序*/// lc codestart
// class Solution
// {
// public:
// vectorint relativeSortArray(vectorint arr1, vectorint arr2)
// {
// unordered_mapint, int hash;
// setint set(arr2.begin(), arr2.end());
// vectorint remain;
// for (const int num : arr1)
// {
// if (set.count(num))
// hash[num];
// else
// remain.push_back(num);
// }
// vectorint 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:vectorint relativeSortArray(vectorint arr1, vectorint arr2){int upper *max_element(arr1.begin(), arr1.end());vectorint freq(upper 1, 0);for (const int num : arr1)freq[num];vectorint 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 codeend结果 复杂度分析
时间复杂度O(mnupper)其中 m 和 n 分别是数组 arr1 和 arr2 的长度。upper 是数组 arr1 的最大值。
空间复杂度O(upper)其中 upper 是数组 arr1 的最大值。即为数组 freq 需要使用的空间。
