8ms concise C++ using unordered_set


  • 41
    K
    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            unordered_set<int> m(nums1.begin(), nums1.end());
            vector<int> res;
            for (auto a : nums2)
                if (m.count(a)) {
                    res.push_back(a);
                    m.erase(a);
                }
            return res;
        }
    };

  • -3

    Hi, your code runs 12ms on my trial.


  • 0
    K

    runtime may vary slightly, try again you can get 8ms..


  • 0

    thanks& you are right :)


  • 0
    X

    allocate memories in advance help a little
    res.reserve(min(nums1.size(), nums2.size()));


  • 0
    S

    edit: nevermind, was looking at unordered_map instead of unordered_set


  • 0
    S

    Sorry for a stupid question.
    why not unordered_set<int> m(nums1->begin(), nums1->end()); ??


  • 0
    W

    @s961206 it's stl vector's function to get iterator, its usage like pointer in array but not this.


  • 0
    R

    I want to know why the for is more quick than foreach?I have test it but i can't understand it.


  • 2
    S

    A possible improvement. Combine "erase" and "count" together to save some time.

    #include <unordered_set>
    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            if (nums1.empty() || nums2.empty()){
                return std::vector<int>();
            }
            std::unordered_set<int> set{nums1.cbegin(), nums1.cend()};
            std::vector<int> intersections;
            for (auto n: nums2){
                if (set.erase(n) > 0){ // if n exists in set, then 1 is returned and n is erased; otherwise, 0.
                    intersections.push_back(n);
                } 
            }
            return intersections;
        }
    };
    

Log in to reply
 

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