两个数组的交际2
1. 题目描述
给你两个整数数组nums1和nums2，请你以数组的形式返回两数组的交集。返回结果中每个元素出现的次数，英语元素在两个数组中都出现的次数一致。可以不考虑输出结果的顺序。
示例
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
2. 解法
2.1 我的解法-双map
一开始我的思路是：我想要统计每个数组中每个元素出现的次数，然后对比这两份统计结果，取其中较小的次数填入答案。
由于要统计元素出现的次数，我想到了map或者数组。以示例为例，定义空的map1和map2。首先遍历nums1，nums1中元素代表map1中的key值，遍历到了，就在map1对应key处加1.所以遍历完两个数组后map1=[2,2]，map2=[0,2]。然后对比两张map，在都有value的地方选取较小的value作为交集中该key出现的次数填入交集。
代码如下：
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {vector<int> ans;map<int,int> m1, m2;for(int r:nums1)//遍历nums，统计各元素出现的次数{++m1[r];} for(int r:nums2){++m2[r];}for(int i=0;i!=(m1.size()<m2.size()?m1.size():m2.size());++i)//循环次数为m中大小较小的值{m1[i]=m1[i]<m2[i]?m1[i]:m2[i];//只选取较小的值保留下来if(m1[i])//如果m[i]处value不为0{for(int j=0;j!=m1[i];++j)以该value为次数填入数据{ans.push_back(i);}}}return ans;}
};
执行用时16ms，内存消耗12.1MB。
2.2 单map，优化一下
如果我只统计一个数组中元素出现的次数，然后遍历另一个数组，以这个数组的元素值为key搜索map。如果map[key]不为0，就代表这两个数组出现了重复元素一次。这个时候–map[key]，将key添加进答案，不就完成这道题了吗？第一次遍历的数组可以选取长度较短的数组。
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {if(nums1.size()>nums2.size()) return intersect(nums2,nums1);//选取较短的数组作为第一个参数vector<int> ans;map<int,int> m1;for(int r:nums1){++m1[r];} for(int r:nums2){if(m1.find(r)->second){ans.push_back(r);--m1[r];}}return ans;}
};
执行用时4ms，内存消耗10.2MB。
2.3 双指针
这里双指针用法与之前类似。之前是快慢指针，在同一个数组中，这里换成了不同数组。首先将两个数组排序。定义两个指针分别指向两个数组的起始位置。解引用指针判断是否相等，相等的话就将该值填入答案，然后两个指针均+1；不等的话，指向较小值的指针++，另一个不动。结束循环的条件为其中一个指针指向了end()。
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(),nums1.end());sort(nums2.begin(),nums2.end());vector<int>::iterator it1 = nums1.begin(), it2 = nums2.begin();vector<int> ans;while(it1!=nums1.end() && it2!=nums2.end()){if(*it1 == *it2){ans.push_back(*it1);++it1;++it2;}else{*it1 < *it2 ? ++it1 : ++it2;}}return ans;}
};
