380. Insert Delete GetRandom O(1)

1:  class RandomizedSet {  
2:  private:  
3:    unordered_map<int, int> mp;  
4:    vector<int> nums;  
5:  public:  
6:    /** Initialize your data structure here. */  
7:    RandomizedSet() {  
8:    }  
9:    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */  
10:    bool insert(int val) {  
11:      if (mp.find(val) != mp.end()) return false;  
12:      nums.push_back(val);  
13:      mp[val] = nums.size()-1;  
14:      return true;  
15:    }  
16:    /** Removes a value from the set. Returns true if the set contained the specified element. */  
17:    bool remove(int val) {  
18:      if (mp.find(val) == mp.end()) return false;  
19:      int i = mp[val];  
20:      int j = nums.size()-1;  
21:      swap(nums[i], nums[j]);  
22:      mp[nums[i]] = i;  
23:      mp.erase(nums[j]);  
24:      nums.pop_back();  
25:      return true;  
26:    }  
27:    /** Get a random element from the set. */  
28:    int getRandom() {  
29:      return nums[rand()%nums.size()];  
30:    }  
31:  };  
32:  /**  
33:   * Your RandomizedSet object will be instantiated and called as such:  
34:   * RandomizedSet obj = new RandomizedSet();  
35:   * bool param_1 = obj.insert(val);  
36:   * bool param_2 = obj.remove(val);  
37:   * int param_3 = obj.getRandom();  
38:   */