[LeetCode]day17 349.两个数组的交集

https://leetcode.cn/problems/intersection-of-two-arrays/description/

题目描述

给定两个数组 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看出）

解法一：暴力解法

最容易想到的就是使用双重循环遍历两个数组，发现有相同元素并且结果数组中没有重复的元素时，就加入结果数组中

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

时间复杂度为$O（n）=n^2$

解法二：使用哈希表

上一篇我们提到过，当需要查询一个数据是否存在于某个集合中时，要先想到使用哈希表

使用数组

由于这道题中，数组中的数据最大为1000，我们可以考虑使用数组
数组的下标对应了每一个数字

• 用set来作为结果数组，因为set本身数据是不可重复的
• 遍历nums1 比如说遍历到5 就将hash[5]改为1
• 遍历nums2 比如说遍历到5 去查找hash[5]是否为1 如果为1，说明num2和nums1中都有这个数 如果并且re数组中没有5，就将它放入结果数组中

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
       unordered_set<int>re;
       int hash[1001]={0};
     for(int i=0;i<nums1.size();i++){
        hash[nums1[i]]=1;
     }
     for(int i=0;i<nums2.size();i++){
        if(hash[nums2[i]]==1){
            re.insert(nums2[i]);
        }
     }
       return vector<int>(re.begin(),re.end());
    }
};

使用set

如果数据更大一些，就可以考虑使用set 其中unordered_set查询效率比较高

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

使用哈希表 时间复杂度 $O(n)=m+n$