C++ 49ms beat 92% by unordered_multimap and vector


  • 0
    M
    class RandomizedCollection {
    public:
        unordered_multimap<int, int> mp;
        vector<pair<int, unordered_multimap<int, int>::iterator>> vals;
    
        /** Initialize your data structure here. */
        RandomizedCollection() {
            srand(time(nullptr));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            auto it = mp.insert({val, vals.size()});
            vals.push_back({val, it});
            return mp.count(val) < 2;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (!mp.count(val))
                return false;
            auto it = mp.find(val);
            int idx = it->second;
            vals[idx] = vals.back();
            vals[idx].second->second = idx;
            vals.pop_back();
            mp.erase(it);
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return vals[rand() % vals.size()].first;
        }
    };
    
    /**
     * Your RandomizedCollection object will be instantiated and called as such:
     * RandomizedCollection obj = new RandomizedCollection();
     * bool param_1 = obj.insert(val);
     * bool param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

Log in to reply
 

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