350. Intersection of Two Arrays II

• Total Accepted: 23510
• Total Submissions: 56283
• Difficulty: Easy

 

Given two arrays, write a function to compute their intersection.

Example:

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

 

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

 

思路：和类似，但注意返回值的区别。

 

另外学习了和的用法。

 

代码：

方法一：利用，复杂度比方法二低。

1 class Solution { 2 public: 3     vector
     
       intersect(vector
      
       & nums1, vector
       
        & nums2) { 4         unordered_map
        
          m; 5         vector
         
           res; 6         for(int i:nums1) m[i]++; 7         for(int i:nums2){ 8             if(m[i]-->0){ 9                 res.push_back(i);10             }11         }12         return res;13     }14 };
         
        
       
      
     

 

 

方法二：

1 class Solution { 2 public: 3     vector
     
       intersect(vector
      
       & nums1, vector
       
        & nums2) { 4         sort(nums1.begin(),nums1.end()); 5         sort(nums2.begin(),nums2.end()); 6         vector
        
          res; 7         int i=0,j=0; 8         while(i
         
          
           nums2[j]?j++:i++;18 }19 }20 return res;21 }22 };