leetcode 350. Intersection of Two Arrays II （两个数组中的重复元素）

题目要求

给定两个数组，找出重复元素，注意和题目349的区别。

题目解析

题目349 leetcode 349 求数组的交集更像是求两个数组的交集（无重复元素），而本道题目是直接取两个数组的重复元素（记次数的），如example1中的2重复了两次。 为什么example2的输出是[4,9]而不是[9,4,9,4]呢？因为两个数组中同时只重复了一次[4,9]。若nums1是[4,9,5,4]那么输出就是[4,9,4]了。根据这个特性，我们使用unordered_map来执行hash的操作。
建立hash表的时候同时记录元素出现的次数，方便统计

主要代码c++

hash法
Time: O(m + n) Space: O(m + n) m,n为数组的大小

class Solution {
    
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int,int>map;vector<int>ans;for(int i=0; i<nums1.size();++i)map[nums1[i]]++; //记录出现的次数！！！for(int i=0; i<nums2.size();++i)if(map[nums2[i]]-->0) // 每次找到一个就减1！！！ans.push_back(nums2[i]);return ans;}
};

排序+双指针法
Sort and two pointers Solution:
Time: O(max(m, n) log(max(m, n))) Space: O(m + n)

class Solution {
    
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(),nums1.end());sort(nums2.begin(),nums2.end());int p1=0, p2=0; // two pointers 双指针法vector<int>res;while(p1<nums1.size()&&p2<nums2.size()){
    if(nums1[p1] == nums2[p2]){
    res.push_back(nums1[p1]);p1++, p2++;}else if(nums1[p1]<nums2[p2])p1++;elsep2++;}return res;  }
};

建议使用hash方法，在数据较多的时候sort+two pointers会非常耗时