547. 两数组的交
样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].要求去重，这样还是稍微有点难度。
暴力搜索
最暴力的方法，对于nums1种的每个元素都去nums2种搜索，看是否存在，如果存在，就把这个数放入结果中，因为要求去重，所以放入的时候还要检查一下是否已经存在，我们可以先对两个数组都进行排序来规避这个问题，显然太暴力了，都懒得写，时间估计肯定超时了。
排序+双指针+手动去重
先排序，然后利用双指针把两个数组种都有的数放入res，除了第一次，每次放入的时候检查一下和上一次放入的是否是相同的，如果是相同的就不再放入了。 我也不知道这个怎么会超时：
vector<int> intersection(vector<int> nums1, vector<int> nums2) {
if(nums1.empty()||nums2.empty())
return vector<int>();
vector<int> res1;
//vector<int> res;
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int n1,n2;
for(n1=0,n2=0;n1<nums1.size()&&n2<nums2.size();)
{
if(nums1[n1]==nums2[n2])
{
if(res1.size()==0||*(res1.end()-1)!=nums1[n1])
res1.push_back(nums1[n1]);
n1++;
n2++;
}
else if(nums1[n1]<nums2[n1]) n1++;
else if(nums2[n2]<nums1[n1]) n2++;
}
return res1;
// write your code here
}set暴力去重+双指针。
依次把所有的数都放入set中（就是去重，排序过的），然后利用双指针遍历即可，这个就相当esay了。
vector<int> intersection(vector<int> nums1, vector<int> nums2)
{
set<int> res1;
set<int> res2;
vector<int> res;
for(auto n:nums1)
{
res1.insert(n);
}
for(auto n:nums2)
{
res2.insert(n);
}
auto beg1=res1.begin();
auto beg2=res2.begin();
auto end1=res1.end();
auto end2=res2.end();
for(;beg1!=end1&&beg2!=end2;)
{
if(*beg1==*beg2)
{
res.push_back(*beg1);
beg1++;
beg2++;
}
else if(*beg1<*beg2)
{
beg1++;
}
else if(*beg1>*beg2)
{
beg2++;
}
}
return res;
}over!
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录