leetcode 两个数组的交集2

> 思路：
> 1.使用哈希表记载第一个数组出现的次数
> 2.创建一个新数组
> 3.遍历第二个数组  将重复的push进新数组 随之哈希表中的该元素的次数-1
> 4.unordered_map的底层是哈希表，元素插入无序，  时间复杂度是O(n） 相比较map底层是红黑树，时间复杂度是O(nlog n）更胜一筹

1
2
3
4
5
6
7

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        //计算频率
        unordered_map<int,int>mp;
        for(auto &ch:nums1)
        {
            mp[ch]++;//计算出现频率
    }

    vector<int>v;
    for(auto &sh:nums2)
    {
        if(mp[sh])
        {
            v.emplace_back(sh);//插入
            mp[sh]--;//mp中sh的次数-1
        }
    }
    return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.使用双指针的方式

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        //排好序的两个数组
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        vector<int>ans;
        int left=0;
        int right=0;
        while(left<nums1.size()&&right<nums2.size())
        {
            if(nums1[left]<nums2[right])
            {
                left++;
            }
            else if(nums1[left]>nums2[right])
            {
                right++;
            }
            else
            {
                ans.emplace_back(nums1[left]);
                left++;
                right++;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

如有错误，多多指教