349. Intersection of Two Arrays

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.

要求返回两个元素的相同部分，因为不需要考虑重复元素的问题,所以没什么难度，用hash-table可以很快解决问题，代码如下:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> hash(nums1.begin(),nums1.end());
        vector<int> res;
        int k=0;
        for(int i=0;i<nums2.size();i++){
            if(hash.count(nums2[i])){
                res.push_back(nums2[i]);
                hash.erase(nums2[i]);
            }
        }
        return res;
    }
};

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 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 2 3 3]
[1 2 3 3 4 5]

要求返回[1,2,3,3]

依然采用hash算法，只不过要记录每个元素在nums1数组中出现的次数，代码如下；

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hash;
        vector<int> res;
        for(int i=0;i<nums1.size();i++)
                hash[nums1[i]]++;
        for(int i=0;i<nums2.size();i++){
            if(hash.find(nums2[i])!=hash.end()&&--hash[nums2[i]]>=0)
                res.push_back(nums2[i]);
        }
        return res;
    }
};

下面考虑follow up:

如果是给出两个排好序的数组，那么从头往后扫一遍对比元素值就可以解决了。

剩下两个容我再想想…………