C++ Vector Map Set


  • 0
    G
    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            srand(time(NULL));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool flag=false;
            v.push_back(val);
            if(!mapNumPos.count(val)) {
                mapNumPos[val]=set<int>();
                flag=true;
            }
            mapNumPos[val].insert(v.size()-1);
            return flag;
            
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            bool flag=false;
            if(mapNumPos.count(val)) {
                flag=true;
                set<int> pos=mapNumPos[val];
                int delPos = *pos.begin();
                int lastPos=v.size()-1;
                int lastNum=v[lastPos];
                
            
                //update vec
                swap(v[delPos], v[lastPos]);
                v.pop_back();
                
                //update map
                //update val pos
                mapNumPos[val].erase(delPos);
                if(mapNumPos[val].size() == 0) {
                    mapNumPos.erase(val);
                }
                
                //update last pos
                if(mapNumPos.count(lastNum)) {
                    mapNumPos[lastNum].erase(lastPos);
                    mapNumPos[lastNum].insert(delPos);
                }
               
            }
            return flag;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int n=v.size();
            int pos = rand()%n;
            int val=v[pos];
            return val;
            
        }
    private:
        vector<int> v;
        unordered_map<int, set<int>> mapNumPos;
    };
    

Log in to reply
 

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