Leetcode 350. Intersection of Two Arrays II

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?

解法一：

 1 class Solution {
 2 public:
 3     vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
 4         vector<int> v;
 5         int len2 = nums2.size();
 6         for(int i = 0; i < len2; i++)
 7         {
 8             for(int j = 0; j < nums1.size(); j++)
 9             {
10                  if(nums2[i] == nums1[j])
11                  {
12                     v.push_back(nums2[i]);
13                     nums1.erase(nums1.begin()+j);
14                     break;
15                  }
16             }
17         }
18         return v;
19     }
20 };

View Code

解法二：

 1 class Solution {
 2 public:
 3     vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
 4         vector<int> intersection;
 5 
 6         if(nums1.empty() || nums2.empty())
 7         {
 8             return intersection;
 9         }
10 
11         sort(nums1.begin(), nums1.end());
12         sort(nums2.begin(), nums2.end());
13 
14 
15         int m = nums1.size();
16         int n = nums2.size();
17 
18         int i = 0,j = 0;
19         while(i < m && j < n)
20         {
21                  if(nums1[i] < nums2[j])
22                  {
23                      i++;
24                  }
25                  else if(nums1[i] > nums2[j])
26                  {
27                      j++;
28                  }
29                  else
30                  {
31                      intersection.push_back(nums1[i]);
32                      i++;
33                      j++;
34                  }
35          }
36 
37 
38         return intersection;
39     }
40 };

View Code

解法三：用hash表, 简单粗暴, 如果是有序的可以不用hash表, 同时扫描两个数组, 找相同的. 如果nums2在磁盘中, 用hash表无影响

 1 class Solution {
 2 public:
 3     vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
 4         if(nums1.size()==0 || nums2.size()==0) return vector<int>();
 5         vector<int> result;
 6         unordered_map<int, int> hash;
 7         for(auto val: nums1) hash[val]++;
 8         for(auto val: nums2)
 9         {
10             if(hash.count(val) && hash[val]>0) result.push_back(val);
11             hash[val]--;
12         }
13         return result;
14     }
15 };

View Code

1. 如果不排序，O(mn)。
2. 如果m和n都在合理范围内，先排序，再一个一个对比，时间复杂度O(nlgn + mlgm + m+n)。
3. 如果m远小于n, 对n排序，m也排序（nlgn+mlgm+m+n），或者m不排序(nlgn + mn)。这两种都差不多。也可以对m不排序，在n里做binary search，这样复杂度降低为nlgn+mlgn, 降很低。
4. 如果n很大，n只能存在disk上。只能把m load到内存，然后n一个一个的读进来，和m对比，这时m可以用hash存，这样复杂度就为O（n）了。