C++ 52ms beating 89% solutions, Real O(1), correct use of unordered_multimap


  • 0
    M

    I saw there are several top rated solutions using unordered_map, but in this case unordered_multimap is more efficient. While there's one existing solution using unordered_multimap, it has a major bug - it didn't check to make sure that we changed the correct entry inside the map inside the remove method. The below code uses the equal_range to make sure we delete the correct entry. It runs in 52ms and beats 89% of the solutions.

    class RandomizedCollection {
        vector<int> data;
        unordered_multimap<int, int> mp;
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool res = true;
            if (mp.find(val) != mp.end()) res = false;
            data.push_back(val);
            mp.insert(make_pair(val, data.size() - 1));
            return res;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto it = mp.find(val);
            if (it == mp.end()) return false;
            int loc = it->second;
            auto ir = mp.equal_range(data.back());
            for (auto irt = ir.first; irt != ir.second; ++irt) {
                if (irt->second == data.size() - 1) {
                    mp.erase(irt);
                    break;
                }
            }
            mp.insert(make_pair(data.back(), loc));
            swap(data[loc], data[data.size() - 1]);
            data.pop_back();
            mp.erase(it);
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return data[rand() % data.size()];
        }
    };
    

  • 0
    A

    The remove function here isn't O(1)?


Log in to reply
 

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