题目描述

给定两个数组，求交集。
1、答案的顺序无所谓
2、交集里的数没有重复

样例

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]. 

思路

审题要注意到交集里的点没有重复。

方法1 暴力求解

最直观的办法是，对数组1中的每个数，遍历检查数组2中是否有相同的数。

复杂度分析

时间复杂度 $O(m)*O(n)$

方法2 用哈希数组保存出现过的数

可以开辟一个足够大的数组做标记，保存每个出现过的数。

复杂度分析

每个数只遍历一次,复杂度为O(m)+O(n)。

C++ 代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

        int hash[100000];
        memset(hash,0,100000);
        vector<int> result;

        for(int i=0;i<nums1.size();i++)
        {
            if(hash[nums1[i]]==0)
                hash[nums1[i]]=1;
        }
        for(int i=0;i<nums2.size();i++)
        {
            if(hash[nums2[i]]== 1){
                auto it=find(result.begin(),result.end(),nums2[i]);
                if(it==result.end())
                {
                    result.push_back(nums2[i]);
                }
            }
        }
        return result;
    }
};

利用查改十分高效的无序容器，代码更简洁:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set(nums1.begin(), nums1.end());
        vector<int> result;
        for (int i=0;i<nums2.size();i++) {
            if (set.find(nums2[i]) != s.end()) {
                result.push_back(nums2[i]);
                set.erase(nums2[i]);
            }
        }
        return result;
    }
};