C++ 75ms solution which beats 98%


  • 0
    S
    class RandomizedSet {
        unordered_map<int,int> m; //val with its index so find takes o(1)
        vector<int> nums;
        
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {
            
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if(m.find(val)!=m.end()) return 0;
            nums.push_back(val);
            m[val]=nums.size()-1;
            return 1;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(m.find(val)==m.end()) return 0;
            int ind=m[val];
            int tmp=nums.back();
            
            //swap the two elements
            if(tmp!=val)
            {
                nums[ind]=tmp;
                m[tmp]=ind;
            }
            nums.pop_back();
            m.erase(val);
            return 1;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            return nums[rand()%nums.size()];
        }
    };
    

Log in to reply
 

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