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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

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<int> intersect(vector<int>& nums1, vector<int>& nums2) {
 4 //         unordered_map<int, int> ctr;
 5 //         vector<int> res;
 6 //         for (auto i : nums1) ctr[i]++;
 7 //         for (auto i : nums2) {
 8 //             if (ctr.count(i) > 0 && ctr[i] > 0) {
 9 //                 ctr[i]--;
10 //                 res.push_back(i);
11 //             }
12 //         }
13 //         return res;
14 //     }
15 // };
16 
17 class Solution {
18 public:
19     vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
20         vector<int> res;
21         
22         sort(nums1.begin(), nums1.end());
23         sort(nums2.begin(), nums2.end());
24         
25         int i1 = 0, i2 = 0;
26         while(i1<nums1.size() && i2<nums2.size()){
27             if(nums1[i1] == nums2[i2]){
28                 res.push_back(nums1[i1]);
29                 i1++;
30                 i2++;
31             }
32             else if(nums1[i1] < nums2[i2]){
33                 i1++;
34             }
35             else{
36                 i2++;
37             }
38         }
39         
40         return res;
41     }
42 };