Intersections of Two Arrays

Leetcode 349

Description:

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

Note: Each element in the result must be unique. The result can be in any order.

Example:

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Idea:

Method 1: sort first, then use the previous solution (Note: previous solution allow duplicates)

space O(1), time O(n lg n)

Method 2: use Hashtable to store nums1 elements, then loop through nums2

space O(n), time O(n)

Code:

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

        unordered_set<int> nums1_element;
        for(auto elem: nums1){
            nums1_element.insert(elem);
        }    

        vector<int> result;
        for(auto elem: nums2){
            auto iter = nums1_element.find(elem) ;
            if(iter != nums1_element.end()){
                result.push_back(elem);
                nums1_element.erase(iter);
            }
        }
        return result;

    }
};

变种：element in result may be the same.