leetcode-349-Intersection of Two Arrays
leetcode-349-Intersection of Two Arrays
题目描述：
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
1、Each element in the result must be unique.
2、The result can be in any order.
要完成的函数：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
说明：
1、给定两个vector，求其交集。交集是一个集合，所以不能出现重复元素，集合不要求顺序。
2、最直接的思路是模仿人类思维，设置两个set，分别存储nums1和nums2的数值。set中没有重复的元素，然后双重循环逐一比较，把相同的值写入结果的vector中。
代码如下：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
set<int>s1(nums1.begin(),nums1.end());
set<int>s2(nums2.begin(),nums2.end());
int size1=s1.size();
int size2=s2.size();
vector<int>res;
if(size1<size2)
{
for(set<int>::iterator iter=s1.begin();iter!=s1.end();iter++)
{
for(set<int>::iterator iter0=s2.begin();iter0!=s2.end();iter0++)
{
if(*iter==*iter0)
{
res.push_back(*iter);
break;
}
}
}
}
else
{
for(set<int>::iterator iter=s2.begin();iter!=s2.end();iter++)
{
for(set<int>::iterator iter0=s1.begin();iter0!=s1.end();iter0++)
{
if(*iter==*iter0)
{
res.push_back(*iter);
break;
}
}
}
}
return res;
}上述代码定义了两个set，把数据装入set，然后双重循环。实测16ms，在所有提交的样例中排名靠后。
我们来看看能够怎样改进。
3、改进1：
我们同样定义两个set，把数据装入set，不过我们把双重循环改成单重循环+set.count()，也许利用内置函数会改善一点效果。（但其实单重循环+set.count()也是双重循环）
代码如下：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
set<int> s1(nums1.begin(),nums1.end());
set<int> s2(nums2.begin(),nums2.end());
vector<int>res;
for(set<int>::iterator iter=s2.begin();iter!=s2.end();iter++)
{
if(s1.count(*iter))
res.push_back(*iter);
}
return res;
}代码简洁很多，实测下降到9ms，beats 46.70% of cpp submissions。
看来set.count()这个函数效果还可以。
4、改进2：
我们能不能只定义一个set，然后依旧单重循环+set.count()。代码如下：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
set<int> s1(nums1.begin(),nums1.end());
vector<int>res;
for(int i=0;i<nums2.size();i++)
{
if(s1.erase(nums2[i]))//如果s1中含有nums2{i}，那么push到res中，并且把这个数从s1中删去，避免下一次处理到重复的数
res.push_back(nums2[i]);
}
return res;
}上述代码实测8ms，beats 70.98% of cpp submissions。
省去了定义一个set和数据装入的过程，多了一点set删去数据的过程，这样子更省时间。
5、改进3：
在discuss区看到大神用了unordered_set，尝试了一下，代码如下：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
unordered_set<int> s1(nums1.begin(),nums1.end());
vector<int>res;
for(int i=0;i<nums2.size();i++)
{
if(s1.erase(nums2[i]))
res.push_back(nums2[i]);
}
return res;
}上述代码实测7ms，beats 97.10% of cpp submissions，比起4中做法更省时。
更省时间是因为set使用了红黑树作为存储的数据结构，unordered_set使用的是哈希表，不讲究顺序，而且哈希表读取数据速度更快。
我们的输出不讲究顺序，只要求读取数据，所以使用unordered_set是一个更好的选择。