My C++ Hash Table Solution


  • 0
    A
    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            vector<int> ret;
            unordered_set<int> set;
            // hash the first array
            for(auto n : nums1)
                set.insert(n);
            for(auto n : nums2) {
                if(set.find(n) != set.end())  // found
                {
                    set.erase(n);       // delete it from hash table
                    ret.push_back(n);
                }
            } 
            return ret;
        }
    };

  • 0
    W

    C++ Apply binary search on the longer array.

     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            vector<int>& n1 = nums1.size() >= nums2.size() ? nums1 : nums2;
            vector<int>& n2 = nums1.size() < nums2.size() ? nums1 : nums2;
            
            sort(n1.begin(), n1.end());
            sort(n2.begin(), n2.end());
            vector<int> res;
            
            for(auto n:n2){
                if((res.empty() || res.back() != n) && binary_search(n1.begin(), n1.end(), n)){
                    res.push_back(n);
                }
            }
            
            return res;
        }

  • 0
    A

    yes, the time complexity of your solution is (m+n)log(n),but use hash table which is O(m+n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.