LT简单题349-两个数组的交集

题目链接

题目描述：

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

方法一：暴力破解+哈希表（C++代码）

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {      //方法一：暴力破解+哈希表
        unordered_set set1, set2;
        for(auto& num : nums1){
            set1.insert(num);
        }
        for(auto& num : nums2){
            set2.insert(num);
        }
        return getIntersection(set1, set2);
    }

    vector getIntersection(unordered_set& set1, unordered_set& set2){
        if(set1.size() > set2.size()){
            return getIntersection(set2, set1);
        }
        vector intersection;
        for(auto& num : set1){
            if(set2.count(num)){
                intersection.push_back(num);
            }
        }
        return intersection;
    }
};

 

时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 O(m+n) 的时间，遍历较小的集合并判断元素是否在另一个集合中需要O(min(m,n)) 的时间，因此总时间复杂度是 O(m+n)。

空间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于两个集合。