C++ 9 lines hash table easy to understand


  • 7
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            vector<string>res;
            unordered_map<string,int>m;
            int min = INT_MAX;
            for(int i = 0; i < list1.size(); i++) m[list1[i]] = i;
            for(int i = 0; i < list2.size(); i++)
                if(m.count(list2[i]) != 0)
                    if(m[list2[i]] + i < min) min = m[list2[i]] + i, res.clear(), res.push_back(list2[i]);
                    else if(m[list2[i]] + i == min) res.push_back(list2[i]);
            return res;
        }
    

  • 0
    H

    brilliant! with perfect run time.But you erase and reload the res everytime you find a smaller one,is there any other way to do this?


  • 1

    @horanweihaoran As you mentioned, clear() operation happens only when we found a smaller one, that is

    1. Two lists share a common interest.
    2. The index sum is smaller than previous one.

    Combined 1 and 2, although clear() is a linear time operation, we can see that the clear() operation will only occur a few times, and in average, it only costs a constant time, that's why the runtime is decent.

    (BTW, clear() is linear, but actually we don't have much data in res (right?), which makes res.clear() itself an O(1) operation.)


Log in to reply
 

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