526互联

两数组的交集|哈希集

发布时间 2023-03-29 12:11:55作者: Coeleone

两个数组的交集

寻找两个数组相同的元素，注意返回元素的唯一性

对应题目349. 两个数组的交集

哈希集合

使用两个哈希集合，第一个保存前一个数组的元素，第二个集合遍历第二个数组，如果发现有相同的元素放入第二个集合中，最后因为要返回数组即将集合转化为数组即可。分析复杂度，需要遍历两个数组所以时间复杂度为\(O(M+N)\)；因此相应的空间复杂度也为\(O(M+N)\)。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> mySet(nums1.begin(),nums1.end());
        /*
        for(int i = 0;i < nums1.size();i++) {
            mySet.insert(nums1[i]);
        }
        */
        unordered_set<int> result;
        for(int i = 0;i < nums2.size();i ++) {
            if(mySet.find(nums2[i]) != mySet.end()) {
                result.insert(nums2[i]);
            }
        }
        vector<int> a(result.begin(),result.end());
        /*
        for(auto &iter:result) {
            a.push_back(iter);
        }
        or
        for(auto iter = result.begin();iter != result.end();iter ++) {
			a.push_back(*iter);
		}
        */
        return a;
}