leetcode-349.两个数组的交集

题源

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] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

思考

思考一

将nums1的元素存入map

然后在nums1中找nums2，找到就存储res中

实现思考一代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //输出结果中的每个元素一定是唯一 的,那么可以用set将nums1去重
        //然后用set在nums2中找到
        vector<int> res;
        unordered_map<int,int> map;
        //由于输出元素是一定的，所以无论nums1中有多少个相同的元素，只需要都置为1
        for(int num : nums1){
            map[num] = 1;
        }
        //在nums2中找到和nums1中一样的元素
        for(int num : nums2){
            if(map[num]){
                //找到了便加到res中
                res.push_back(num);
                //避免重复添加，减一
                map[num]--;
            } 
        }
        return res;
    }
};

在这里插入图片描述

思考一代码时间复杂度分析

将nums作为存入map中需要耗费O(n)的时间复杂度

在nums2中找到和nums1中一样的元素也需要耗费O(n)的时间复杂度

综合来看，这是一个时间复杂度为O(n)的算法

思考二

既然输出结果中的每个元素一定是唯一的,那么可以用set将nums1去重

然后用set在nums2中找到存在于nums1中的元素，找到就存入res

实现思二代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 创建一个 unordered_set 来存储 nums1 中的所有元素
        unordered_set<int> nums1Set(nums1.begin(), nums1.end());

        // 用于存放结果的 vector
        vector<int> res;

        // 遍历 nums2 中的每个元素
        for (int num : nums2) {
            // 如果元素在 nums1Set 中存在，且结果中还没有这个元素
            if (nums1Set.count(num) > 0 && find(res.begin(), res.end(), num) == res.end()) {
                // 将元素添加到结果中
                res.push_back(num);
            }
        }

        return res;
    }
};

在这里插入图片描述

思考二代码时间复杂度分析

find(res.begin(), res.end(), num) == res.end())本身是o(n)的时间复杂度

再加上遍历nums2的for()循环

这个算法也就会耗费o(n^2)的时间复杂度

思考三

思考二中用vector容器来保存答案，需要用find去保证添加进vector的元素唯一

现在我可以用set来保存答案，就不需要这个O(n)时间复杂度的find()方法

思考三代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //既然输出结果中的每个元素一定是唯一 的,那么可以用set将nums1去重
 
        //然后用set存储最终的答案,也免去的答案去重的步骤
        unordered_set<int> setRes;
        //用set将nums1去重
        unordered_set<int> set(nums1.begin(),nums1.end());
        for(int num : nums2){
            if(set.count(num)){
                //用set保证集合的元素唯一
                setRes.insert(num);
            }
        }
        return vector<int>(setRes.begin(),setRes.end());

    }
};