两个数组的交集,写一段代码,找到两个数组的交集数组
30.两个数组的交集II
给你两个整数数组nums1和nums2。请将两个数组的交集作为一个数组返回。返回结果中每个元素的出现次数应该与该元素在两个数组中的出现次数一致(如果出现次数不一致,考虑取较小的值)。输出结果的顺序可以忽略。
示例1:
输入:nums1=[1,2,2,1],nums2=[2,2]
输出:[2,2]
示例2:
输入:nums1=[4,9,5],nums2=[9,4,9,8,4]
输出:[4,9]
提示:
1=nums1.length,nums2.length=1000
0=nums1[i],nums2[i]=1000
高级:
如果给定的数组已经排序了呢?你将如何优化你的算法?
如果nums1的大小小于nums2,用哪种方法比较好?
如果nums2的元素都存储在磁盘上,内存有限,无法一次性将所有元素加载到内存中,该怎么办?
资料来源:LeetCode
链接:https://leetcode.cn/problems/intersection-of-two-arrays-ii
版权归领网所有。商业转载请联系官方授权,非商业转载请注明出处。
方案一:哈希表思路一:用两个哈希表统计每个元素在两个数组中出现的次数,然后选择在两个哈希表中都出现但次数较少的元素。
想法2:用一个哈希表统计每个元素在一个数组中出现的次数,然后遍历另一个数组。如果当前元素在哈希表中出现的次数大于0,则将该元素放入结果中,并将数字减1。
代码如下:
#包含位/标准数据。h
使用命名空间std
类别解决方案
{
公共:
向量int intersect(向量int nums1,向量int nums2)
{
std:unordered_map int,int m1
std:unordered_map int,int m2
for(自动编号:nums1)
{
m1[n];
}
用于(自动编号:nums2)
{
m2[n];
}
STD:vector int ans;
用于(自动x : m1)
{
if (m2.find(x.first)!=m2.end())
{
ans.insert(ans.end(),std:min(m1[x.first],m2[x . first]);
}
}
返回ans
}
};
#包含位/标准数据。h
使用命名空间std
类别解决方案
{
公共:
向量int intersect(向量int nums1,向量int nums2)
{
std:unordered_map int,int m1
std:unordered_map int,int m2
for(自动编号:nums1)
{
m[n];
}
STD:vector int ans;
用于(自动x : nums2)
{
if (m[x] 0)
{
m[x]-;
ans . push _ back(x);
}
}
返回ans
}
};方法二:暴力解决的想法:
遍历数组1,然后每次从数组2开始比较。当找到一个相等的元素时,它被从数组2中删除,然后数组1的索引向后移动。
类别解决方案{
公共:
向量整数相交(向量整数1,向量整数2) {
矢量int ret
for(size _ t I=0;I nums 1 . size();我)
{
for(size _ t j=0;j nums 2 . size();j)
{
if ( (nums1[i]==nums2[j]))
{
ret . push _ back(num S1[I]);
nums 2 . erase(nums 2 . begin()j);
打破;
}
}
}
返回ret
}
};方法三:双指针排序的思想:
排序2个数组,用2个指针遍历2个数组。如果它们不相等,将较小元素的指针向右移动。如果相等,将当前元素放入结果数组,并将两个指针都向右移动。代码如下:
类别解决方案{
公共:
向量整数相交(向量整数1,向量整数2) {
sort(nums1.begin()、num S1 . end());
sort(nums2.begin()、nums 2 . end());
int length1=nums1.size(),length 2=nums 2 . size();
向量int交集;
int index1=0,index 2=0;
while(索引1长度1索引2长度2) {
if(num S1[index 1]num S2[index 2]){
索引1;
} else if(num S1[index 1]num S2[index 2]){
索引2;
}否则{
intersection . push _ back(num S1[index 1]);
索引1;
索引2;
}
}
返回路口;
}
};
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。