Use unordered_multimap and vector


  • 0
    F

    the most import is remove element,we need to keep map index is sequence

    class RandomizedCollection {
    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({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) {
            bool res = false;
            unordered_multimap<int,int>::iterator it = mp.find(val);
            if(it != mp.end())
            {
                res = true;
                int len = data.size()-1;
                int locat = it->second;
                if(locat != len)
                {
                    data[locat] = data[len];
                    mp.find(data[len])->second = it->second;
                }
                data.pop_back();
                mp.erase(it);
            }
            return res;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
           int index = rand()% data.size();
           return data[index];
            
        }
    private:
        unordered_multimap<int,int> mp;
        vector<int> data;
    };
    

    */


Log in to reply
 

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