C++ unordered_map and vector. is this real O(1)?


  • 0
    G

    using vector<int>numpool to store all the number
    using unordered_map<int,set<int>>mp; key: inserted val, value: index in vector<int>numpool
    Because set can automatically sort, dose anybody can tell my solution is real O(1)?

    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) {
                numpool.push_back(val);
                mp[val].insert(numpool.size()-1);
                return mp[val].size()==1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if(mp[val].size()==0)
                return false;
                
                auto itr=--mp[val].end();
                int indx=*itr;
                //delete index
                mp[val].erase(itr);
                // swap value and update index
                if(indx!=numpool.size()-1){
                int tempval=numpool.back();
                numpool[indx]=tempval;
                mp[tempval].insert(indx);
                mp[tempval].erase(--mp[tempval].end());
                }
                
                numpool.pop_back();
                return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return numpool[rand()%numpool.size()];
        }
        
        vector<int>numpool;
        unordered_map<int,set<int>>mp;
    };
    

Log in to reply
 

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