题源
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());}
};
思考三代码时间复杂度分析
由于只用了一个for()循环,花费了O(n)的时间复杂度
虽然最后将set转为vector会花费O(m)的时间复杂度
综合依然只用了O(n)的时间复杂度,但不知道为什么会耗时这么多