C++ 52ms Solution using map and vector with explanation


  • 0
    A

    Adding and removing from map is O(1) so that's simple enough, we
    store the index in the vector for the insert, when we remove we don't remove from the vector because that will offset all the indices, instead we mark them as deleted using the bool in the pair. Now getRandom just needs to test if the value found is deleted, if it is get another.

    class RandomizedCollection {
        map<int, vector<int>> m;
        vector<pair<int, bool>> r;
    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) {
            m[val].push_back(r.size());
            r.push_back(pair<int,bool>(val, false));
            return m.find(val) == m.end();
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (m.find(val) != m.end()) {
                int i = m[val].back();
                m[val].pop_back();
    
                r[i].second = true;
                if (m[val].size() == 0) {
                    m.erase(val);
                }
                return true;
            }
            return false;
        }
    
        /** Get a random element from the collection. */
        int getRandom() {
            int ran =  rand() % r.size();
    
            while(r[ran].second == true)
                ran =  rand() % r.size();
    
            return r[ran].first;
        }
    };
    

Log in to reply
 

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