leetcode-349.两个数组的交集

2024/10/26 22:01:16 来源：https://blog.csdn.net/qq_62893047/article/details/140358384 浏览: 次关键词：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中有多少个相同的元素，只需要都置为1for(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());// 用于存放结果的 vectorvector<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());}
};