[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$