c++ Easy Solution


  • 0
    W

    The only thing need to concern is remove, swap the removed node with the last node in vector, then pop_back take O(1) time.

    class RandomizedSet {
    public:
        vector<int> nums;
        unordered_map<int, int> dict;
        /** 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(dict.find(val)!=dict.end()) return false;
            dict[val] = nums.size();
            nums.push_back(val);
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(dict.find(val)==dict.end()) return false;
            dict[nums.back()] = dict[val];
            swap(nums.back(),nums[dict[val]]);
            nums.pop_back();
            dict.erase(val);
            return true;
        }
        
        /** 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.