349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

方法一：

思路：

取数组1和数组2中不重复的元素：用一个set s1存第一个数组的元素，再用一个set s2存第二个数组的元素

计算s1和s2中的元素的总出现次数：然后用一个map<int,int> m，遍历s1和s2，将对应的元素的映射加1

这样的话，映射中大于1的元素就是数组1和数组2中重复的元素了

代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1;
        for(int i=0;i<nums1.size();i++)        //数组1存到set s1中
        {
            s1.insert(nums1[i]);
        }
        
        set<int> s2;
        for(int i=0;i<nums2.size();i++)       //数组2存到set s2中
        {
            s2.insert(nums2[i]);
        }
        
        map<int,int> m;
        set<int>::iterator temp;
        for(temp=s1.begin();temp!=s1.end();temp++)       //将s1中的元素的映射加1
        {
            m[*temp]++;
        }
        for(temp=s2.begin();temp!=s2.end();temp++)       //将s2中的元素的映射加1
        {
            m[*temp]++;
        }
        vector<int> res;
        for(int i=0;i<nums1.size();i++)
        {
            s2.insert(nums1[i]);
        }
        for(temp=s2.begin();temp!=s2.end();temp++)     //如果映射大于1，就存到要返回的数组中
        {
            if(m[*temp]>1)
                res.push_back(*temp);
        }
        
        return res;
    }
};

效率不高：

方法二：

思路：

将数组1排序，并去掉重复的元素

将数组2排序，并去掉重复的元素

用一个指针n1指向数组1的开始，用一个指针n2指向数组2的开始

在n1和n2不越界的情况下，不断循环判断*n1和*n2的大小关系：

如果相等，则把元素输入到要返回的数组，n1++,n2++

如果*n1>*n2，则n2++直到不满足前面条件为止

如果*n2>*n1，则n1++直到不满足前面条件为止

这样，就可以把所有重复的元素找出来了

代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> rev;
        if(nums1.empty() ||nums2.empty())             //如果数组其中一个为空，直接返回空数组
            return rev;
        sort(nums1.begin(),nums1.end());                    //将数组1排序
        vector<int>::iterator temp;
        for(temp=nums1.begin();temp<nums1.end()-1;)        //去掉数组1中重复的元素
        {
            if(*temp==*(temp+1))
            {
                nums1.erase(temp);
            }
            else
                temp++;
        }    
        sort(nums2.begin(),nums2.end());                    //将数组2排序
        for(temp=nums2.begin();temp<nums2.end()-1;)        //去掉数组2中重复的元素
        {
            if(*temp==*(temp+1))
            {
                nums2.erase(temp);
            }
            else
                temp++;
        }
        vector<int>::iterator n1=nums1.begin(),n2=nums2.begin();    //设定指针n1和n2
        while(n1<nums1.end() &&n2<nums2.end())                //在n1和n2不越界的条件下循环
        {
            if(*n1==*n2)                                       //*n1==*n2的情况
            {
                rev.push_back(*n1);
                n1++;
                n2++;
            }
            while(*n1>*n2 && n2<nums2.end())                   //*n1>*n2的情况
                n2++;
            while(*n1<*n2 &&n1<nums1.end() )                   //*n1<*n2的情况
                n1++;
        }
        return rev;
    }
};

效率非常高：