350. 两个数组的交集 II-7月13日
2021-04-19 03:29
标签：width 数组的交集 复杂 学习 temp 图片 元素 bsp pre 350. 两个数组的交集 II 我最开始的思路：外循环遍历数组1，对于每个数组1的元素，在数组2中找是否有相同的元素，若有添加到新数组并从数组2删除。时间复杂度是m*n。 借用哈希表，可以降低再数组2中找相同元素的复杂度，代价是需要是为数组2构造一个哈希表。其中哈希表的key是元素的值，value是元素在数组中出现的次数。若数组2中存在与当前遍历的数组1中相同的元素，把key值-1。时间复杂度是m+n。空间复杂度是n（哈希表）。 记住可以借助哈希表来降低查找元素的时间复杂度 350. 两个数组的交集 II-7月13日 标签：width 数组的交集 复杂 学习 temp 图片 元素 bsp pre 原文地址：https://www.cnblogs.com/BoysCryToo/p/13291976.html题目
我的思路
我的实现
class Solution {
public:
vectorint> intersect(vectorint>& nums1, vectorint>& nums2) {
vectorint> results;
for(auto it : nums1){
auto temp_it=find(nums2.begin(),nums2.end(),it);
if(temp_it!=nums2.end()){
results.push_back(it);
nums2.erase(temp_it);
}
}
return results;
}
};
//外循环遍历数组1，对于每个数组1的元素，在数组2中找是否有相同的元素，若有添加到新数组并从数组2删除；
//1.如果给定的数组已经排好序，可以用滑动窗口的思想：从小到大遍历数组1中的元素，在数组2中设一个指针，最开始指向数组2最小的元素。若当前遍历的数组1中的元素与数组2中指针当前指向的元素不匹配，那么指针右移；若匹配（相同），数组1中的指针与数组2中的指针同时右移。直到两个指针都达到最右端
//3.数组2元素的遍历作为外循环，减少IO次数
拓展学习
文章标题：350. 两个数组的交集 II-7月13日
文章链接：http://soscw.com/index.php/essay/76489.html