Intersection of Two Arrays

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的特性 利用set的性质，注意在找到对应的数的时候，从set中删除这些数。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;

        unordered_set<int> iset(nums1.begin(), nums1.end());

        for(auto num2:nums2){
            if(iset.find(num2) != iset.end())
                res.push_back(num2);
                iset.erase(num2);
        }

        return res;
    }
};

解法二:排序+two pointers

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() || nums2.empty())
            return {};

        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());


        int i = 0, j = 0;

        set<int> res;
        while(i < nums1.size() && j < nums2.size() ){
            if(nums1[i] < nums2[j])
                i++;
            else if(nums1[i] > nums2[j])
                j++;
            else{
                res.insert(nums1[i]);
                i++;
                j++;
            }
        }

        return vector<int> (res.begin(), res.end());
    }
};

解法3：利用set+binary_search 将其中的一个数组排序，遍历另一个数组，查找是否在排序的数组中存在(lower_bound)，时间复杂度$$O(nlogn)$$

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] [1, 1]}, {[1,2] [1,1]} 我们需要的是[1]，如果没有判断大小，会返回[1, 1].

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() || nums2.empty())
            return vector<int> ();
        vector<int> res;

        if(nums1.size() < nums2.size()){
            return intersect(nums2, nums1);
        }

        unordered_map<int, int> imap;
        for(auto num1:nums1)
            imap[num1]++;

        for(auto num2:nums2){
        //此处需要注意的是imap.count(num) > 0,只能说明这个key存在于map中，count返回的是这个key在map中出现的次数，由于map中的key只能出现一次，所以只能为1或0.
            if(imap.count(num2) > 0 && imap[num2] > 0){
                res.push_back(num2);
                imap[num2]--;
            }
        }
        return res;
    }
};

解法2：利用sort + two pointers。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() || nums2.empty())
            return {};
        vector<int> res;

        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;

        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] < nums2[j])
                ++i;
            else if(nums1[i] > nums2[j])
                ++j;
            else{
                res.push_back(nums1[i]);
                ++i;
                ++j;
            }
        }
        return res;

    }
};