350. 两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？如果 nums1 的大小比 nums2 小很多，哪种方法更优？如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
第一种，比较简单易懂：
vector<int>intersect(vector<int>&nums1, vector<int>&nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
intsize1=nums1.size();
intsize2=nums2.size();
intp1=0, p2=0;
vector<int>result;
//result.reserve(size1 > size2 ? size2 : size1);//加上这一句，并不一定会更快一点。
while (p1<size1&&p2<size2) //很重要
{
if (nums1[p1] ==nums2[p2])
{
result.push_back(nums1[p1]);
p1++;
p2++;
}
elseif (nums1[p1] <nums2[p2])
{
p1++;
}
else
{
p2++;
}
}
returnresult;
}
第二种直接在数组上查找
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
vector<int>::iterator it;
for(int i=0;i<nums1.size();i++)
{
it=find(nums2.begin(),nums2.end(),nums1[i]);
if(it!=nums2.end())//查找到元素
{
res.push_back(*it);
nums2.erase(it);//删除元素
}
}
return res;
}
第三中，利用map来进行比对
vector<int>intersect(vector<int>&nums1, vector<int>&nums2) {
if (nums1.size() >nums2.size()) swap(nums1, nums2);//用元素少的数组元素查找
map<int, int>a;
for (inti=0; i<nums2.size(); i++)//初始化map
{
if (!a.count(nums2[i]))
a.insert(map<int, int>::value_type(nums2[i], 1));
elsea[nums2[i]]++; //统计相同元素的个数
}
vector<int>res;
for (inti=0; i<nums1.size(); i++)
{
if (a.count(nums1[i])) //如果有
{
if (a[nums1[i]] !=0)
{
res.push_back(nums1[i]);
a[nums1[i]]--;
}
}
}
returnres;
}
第四种,unordered_map更快速
vector<int>intersect(vector<int>&nums1, vector<int>&nums2) {
// 建立set
unordered_map<int,int>s; // 查找快 和前边区别在于需要记录出现次数
for(auton:nums1)
{
s[n]++;
}
// 遍历nums2判断在不在set 里边 在就是交集
vector<int>ans;
for(auton:nums2)
{
autoit=s.find(n);
if(it!=s.end() &&it->second>0) // 存在且次数大于0 才可以加入
{
ans.push_back(n);
it->second--; // 用一次次数减一
// s.erase(it); // 删除已经存在的防止多次输出相同的元素
}
}
returnans;
}
