9ms C++ solution using unordered_multiset


  • 0
    N

    Storing the smaller vector in unordered_multiset can reduce time from 13ms to 9ms.
    Time complexity O(m + n), Space complexity O(min(m, n)) excluding input and output.

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int> ans;
            if(nums1.size() < nums2.size()){
                unordered_multiset<int> S(nums1.begin(), nums1.end());
                for(int i = 0;i < nums2.size();++i){
                    unordered_multiset<int>::iterator iter = S.find(nums2[i]);
                    if(iter != S.end()){
                        ans.push_back(nums2[i]);
                        S.erase(iter);
                    }
                }
            }else{
                unordered_multiset<int> S(nums2.begin(), nums2.end());
                for(int i = 0;i < nums1.size();++i){
                     unordered_multiset<int>::iterator iter = S.find(nums1[i]);
                    if(iter != S.end()){
                        ans.push_back(nums1[i]);
                        S.erase(iter);
                    }
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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