做软件需要网站有哪些,哪家建站好,系统开发与网站开发,永久免费云linux服务器网页https://leetcode.cn/problems/intersection-of-two-arrays/description/
题目描述
给定两个数组 nums1 和 nums2 #xff0c;返回它们的交集。 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序 。
示例 1#xff1a;
输入#xff1a;nums1 [1,2,2,1…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:vectorint intersection(vectorint nums1, vectorint nums2) {vectorintre;for(int i0;inums1.size();i){for(int j0;jnums2.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 Onn^2 Onn2 解法二使用哈希表
上一篇我们提到过当需要查询一个数据是否存在于某个集合中时要先想到使用哈希表
使用数组
由于这道题中数组中的数据最大为1000我们可以考虑使用数组 数组的下标对应了每一个数字
用set来作为结果数组因为set本身数据是不可重复的遍历nums1 比如说遍历到5 就将hash[5]改为1遍历nums2 比如说遍历到5 去查找hash[5]是否为1 如果为1说明num2和nums1中都有这个数 如果并且re数组中没有5就将它放入结果数组中
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setintre;int hash[1001]{0};for(int i0;inums1.size();i){hash[nums1[i]]1;}for(int i0;inums2.size();i){if(hash[nums2[i]]1){re.insert(nums2[i]);}}return vectorint(re.begin(),re.end());}
};使用set
如果数据更大一些就可以考虑使用set 其中unordered_set查询效率比较高
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setintre;unordered_setinthash;for(int i0;inums1.size();i){hash.insert(nums1[i]);}for(int i0;inums2.size();i){if(hash.find(nums2[i])!hash.end()re.find(nums2[i])re.end()){re.insert(nums2[i]);}}return vectorint(re.begin(),re.end());}
};使用哈希表 时间复杂度 O ( n ) m n O(n)mn O(n)mn
