题目

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

示例 1：

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

示例 2：

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

说明：

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

分析与题解

暴力遍历

将一个数组的元素在另一个数组种遍历。需要注意的是，因为输出元素唯一，所以每次求得的相交元素需要确保不在输出数组中时，才可以push_back.

class Solution {
private:
    static int findnumber(vector<int>& nums, int s){
        int len = nums.size();
        for(int i=0;i<len;i++){
            if(nums[i]==s)
                return s;
        }
        return -1;
    }
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<int> res;
        if(len1==0 || len2==0)
            return res;
        if(len1>len2){
            for(int j=0;j<len2;j++){
                int tmp = findnumber(nums1, nums2[j]);
                if(tmp!=-1 && findnumber(res, tmp)==-1)
                    res.push_back(tmp);
            }
        }else{
            for(int j=0;j<len1;j++){
                int tmp = findnumber(nums2, nums1[j]);
                if(tmp!=-1 && findnumber(res, tmp)==-1)
                    res.push_back(tmp);
            }
        }
        return res;
        
    }
};

无序集合

考虑到输出元素不存在相同元素，所以使用实值和键值相同的集合，来处理相同的元素。
其优点如下：

• 使用无序集合而非一般集合或无序图，节约了时空
• 在检索无序集合时，将检索到的元素删去，而不是遍历answer数组，面对越大规模的问题，该方法效率越优。

代码如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        //集合实值和键值的相同，键值相同的元素会合并
        unordered_set<int> tmp(nums1.begin(),nums1.end());
        /*
        //另一种初始化num1的方法
        //不过第一种执行时间更快
        for(int i:nums1)
            tmp.insert(i);
        */
        for(int i:nums2){
            auto p = tmp.find(i);
            if(p!=tmp.end()){
                //表示查找到了相交元素
                res.push_back(i);
                //同时将相交元素从集合中剔除
                tmp.erase(i);
            }
        }
        return res; 
    }
};