手机有软件做ppt下载网站有哪些内容吗,免费整套ppt模板下载网站,注册贸易公司需要什么条件,域名查找原题链接
难度#xff1a;easy\color{Green}{easy}easy 题目描述
给你两个整数数组 nums1nums1nums1 和 nums2nums2nums2 #xff0c;请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数#xff0c;应与元素在两个数组中都出现的次数一致#xff08;如果出现…原题链接
难度easy\color{Green}{easy}easy 题目描述
给你两个整数数组 nums1nums1nums1 和 nums2nums2nums2 请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。
示例 1
输入nums1 [1,2,2,1], nums2 [2,2]
输出[2,2]示例 2:
输入nums1 [4,9,5], nums2 [9,4,9,8,4]
输出[4,9]提示
1nums1.length,nums2.length10001 nums1.length, nums2.length 10001nums1.length,nums2.length10000nums1[i],nums2[i]10000 nums1[i], nums2[i] 10000nums1[i],nums2[i]1000
** 进阶 **
如果给定的数组已经排好序呢你将如何优化你的算法如果 nums1nums1nums1 的大小比 nums2nums2nums2 小哪种方法更优如果 nums2nums2nums2 的元素存储在磁盘上内存是有限的并且你不能一次加载所有的元素到内存中你该怎么办 算法
(排序双指针) O(nm)O(nm)O(nm)
排序。双指针遍历两个数组如果 ·nums1 小1的下标右移nums2 小2右移。如果相等加入目标数组直到退出循环。
复杂度分析 时间复杂度O(mn)O(m n)O(mn)。 空间复杂度 : O(min(mn))O(min(m n))O(min(mn))
C 代码
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());vectorint res;int left 0, right 0;while (left nums1.size() right nums2.size()) {if (nums1[left] nums2[right])left ;else if (nums1[left] nums2[right]) {res.push_back(nums1[left]);left , right ;} else {right ;}}return res; }
};算法2
(集合)
使用数据结构 unordered_multiset 存储 nums1 中的每个元素。遍历数组 nums2 如果在 集合中把该值加入答案并且在集合中删除该值。
复杂度分析
时间复杂度O(n)O(n)O(n)。
C 代码
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {unordered_multisetint S;vectorint res;for (int x : nums1) S.insert(x);for (int x : nums2)if (S.count(x)){res.push_back(x);S.erase(S.find(x));}return res;}
};
