本文共 2843 字，大约阅读时间需要 9 分钟。

/***************************************************************************************** Given two arrays, write a function to compute their intersection.** Example:* Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].** Note:* Each element in the result must be unique.* The result can be in any order.****************************************************************************************///用set#include "stdafx.h"#include 
   
    #include 
    
     #include 
     
      using namespace std;vector
      
        intersection(vector
       
         &num1, vector
        
          &num2){ set
         
          s1, s2; vector
          
           result; auto iter = num1.begin(); for (; iter != num1.end(); ++iter) s1.insert(num1[*iter]); auto iter2 = num2.begin(); for (; iter2 != num2.end(); ++iter2) if (s1.find(*iter2) != s1.end())//说明在s1中找到了相同的数 s2.insert(*iter2);//插入s2中 auto iter3 = s2.begin();//s2中全是查找相同的元素，且没有重复的值 for (; iter3 != s2.end(); ++iter3) result.push_back(*iter3); return result;}
          
         
        
       
      
     
    
   

用哈希表

class Solution {    public:    vector
   
     intersection(vector
    
     & nums1, vector
     
      & nums2) {       unordered_map
      
        m;       vector
       
         res;       for (int i=0;i
        
         0) { res.push_back(nums2[i]); m[nums2[i]]=0; } } return res; }};
        
       
      
     
    
   

主要下面题目的不同

/*****************************************************************************

* * 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 num2’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? * *****************************************************************************/

哈希表,时间复杂度O(N),空间O(N)

class Solution {public:   vector
   
     intersect(vector
    
     & nums1, vector
     
      & nums2) {      unordered_map
      
        m;      vector
       
         res;      for (int i=0;i
        
         0) { res.push_back(nums2[i]); m[nums2[i]]--; } } return res;}};
        
       
      
     
    
   

排序，无额外空间复杂度

class Solution {public:   vector
   
     intersect(vector
    
     & nums1, vector
     
      & nums2) {      vector
      
        res;      sort(nums1.begin(),nums1.end());      sort(nums2.begin(),nums2.end());      int n1=nums1.size(),n2=nums2.size();      int i=0,j=0;      while (i
       
        
         nums2[j]) j++; else i++; } return res;}};
        
       
      
     
    
   

转载地址：http://iidoi.baihongyu.com/