/***************************************************************************************
*
* 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 <iostream>
#include <vector>
#include <set>
using namespace std;
vector<int> intersection(vector<int> &num1, vector<int> &num2)
{
    set<int>s1, s2;
    vector<int>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<int> intersection(vector<int>& nums1, vector<int>& nums2) {
       unordered_map<int,int> m;
       vector<int> res;
       for (int i=0;i<nums1.size();i++)
           m[nums1[i]]=1;
       for (int i=0;i<nums2.size();i++) {
           if (m[nums2[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<int> intersect(vector<int>& nums1, vector<int>& nums2) {
      unordered_map<int,int> m;
      vector<int> res;
      for (int i=0;i<nums1.size();i++)
           m[nums1[i]]++;
       for (int i=0;i<nums2.size();i++) {
           if (m[nums2[i]]>0) {
               res.push_back(nums2[i]);
               m[nums2[i]]--;
           }
       }
       return res;
}
};

排序，无额外空间复杂度

class Solution {
public:
   vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
      vector<int> 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<n1&&j<n2) {
          if (nums1[i]==nums2[j]) {
              res.push_back(nums1[i]);
              i++;j++;
          }
          else if (nums1[i]>nums2[j])
            j++;
          else 
            i++;
      }
    return res;
}
};