题目描述：

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?

 

要完成的函数：

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 

 

说明：

1、这道题给定两个vector，要求返回两个vector的交集，比如nums1=[1,2,2,1]，nums2=[2,2]，返回的交集是[2,2]，其中有多少个相同的元素就返回多少个。返回的交集不讲究顺序。

2、这道题看完题意，熟悉leetcode的同学应该会马上想到先排序，排序之后的两个vector来比较，时间复杂度会下降很多。

如果不排序，那就是双重循环的做法，O(n^2)，时间复杂度太高了。

先排序再比较的做法，代码如下：（附详解）

vector
     
       intersect(vector
      
       & nums1, vector
       
        & nums2)     {        sort(nums1.begin(),nums1.end());//给nums1排序，升序        sort(nums2.begin(),nums2.end());//给nums2排序，升序        int s1=nums1.size(),s2=nums2.size(),i=0,j=0;//i表示nums1元素的位置，j表示nums2元素的位置        vector
        
         res;//存储最后结果的vector        while(i
         
          
           =nums2[j] i++; if(i==s1)//如果i已经到了nums1的外面，那么结束比较 break; } else if(nums1[i]>nums2[j]) { while(nums1[i]>nums2[j]&&j
           
            =nums1[i] j++; if(j==s2)//如果j已经到了nums2的外面，那么结束比较 break; } if(nums1[i]==nums2[j])//如果刚好相等，那么插入到res中，更新i和j的值 { res.push_back(nums1[i]); i++; j++; } } return res; }
           
          
         
        
       
      
     

上述代码实测7ms，beats 98.05% of cpp submissions。