Design a data structure that supports all following operations in average O(1) time.

 

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

 

Example:

// Init an empty set.RandomizedSet randomSet = new RandomizedSet();// Inserts 1 to the set. Returns true as 1 was inserted successfully.randomSet.insert(1);// Returns false as 2 does not exist in the set.randomSet.remove(2);// Inserts 2 to the set, returns true. Set now contains [1,2].randomSet.insert(2);// getRandom should return either 1 or 2 randomly.randomSet.getRandom();// Removes 1 from the set, returns true. Set now contains [2].randomSet.remove(1);// 2 was already in the set, so return false.randomSet.insert(2);// Since 2 is the only number in the set, getRandom always return 2.randomSet.getRandom(); 

---

1. 对于insert和remove，需要在O(1)的时间内查看该value是否存在，并insert/remove该value，因此考虑hash table。 2. 对于getRandom，考虑用array来实现，因为：1）access每个元素的probablity相同；2）可以在O(1)时间内access任意元素。

1 class RandomizedSet { 2 public: 3     /** Initialize your data structure here. */ 4     RandomizedSet() { 5          6     } 7      8     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ 9     bool insert(int val) {10         if(map.find(val)==map.end()){ //val not presented in the set11             map[val]=data.size();12             data.push_back(val);13             return true;14         }15         16         return false;17     }18     19     /** Removes a value from the set. Returns true if the set contained the specified element. */20     bool remove(int val) {21         if(map.find(val)!=map.end()){ // val presented in the set22             int index = map[val];23             map.erase(val);24             25             //swap the index of the removed value with the last element's index26             int lastIndex = data.size()-1;27             if(index!=lastIndex){28                 map[data[lastIndex]] = index;29                 data[index]=data[lastIndex];30             }31             data.pop_back();32             return true;33         }34         35         return false;36     }37     38     /** Get a random element from the set. */39     int getRandom() {40         return data[rand()%data.size()];41     }42 private:43     vector
      
        data;           //data[index] = val44     unordered_map
       
         map; //map[val] = index45 };46 47 /**48  * Your RandomizedSet object will be instantiated and called as such:49  * RandomizedSet obj = new RandomizedSet();50  * bool param_1 = obj.insert(val);51  * bool param_2 = obj.remove(val);52  * int param_3 = obj.getRandom();53  */
       
      

 

Remove分兩步： 

1. 把val从hash table里除去，hash  table里的key是val，value是array里相应的index。

2.把val从array里除去，其中要除去的index是从hash table里查出的。具体做法是：将array[index]和array的最后的index互换，然后将array的size减一。因为array[index]和array[size-1]互换，hash table里的array[index] val也需要更新。

注意：当index是size-1时，不需要做：array[index]和array[size-1]互换，hash table里的array[index] val更新

 

方法二：

先将hash table更新，然后把hash table和array里的元素remove掉

1 class RandomizedSet { 2 public: 3     /** Initialize your data structure here. */ 4     RandomizedSet() { 5          6     } 7      8     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ 9     bool insert(int val) {10         if(map.find(val)!=map.end()){ //val already exists11             return false;12         }13         array.push_back(val);14         map[val]=array.size()-1;15         return true;16     }17     18     /** Removes a value from the set. Returns true if the set contained the specified element. */19     bool remove(int val) {20         if(map.find(val)==map.end()){ //val not exist21             return false;22         }23         24         int index=map[val];25         map[array[array.size()-1]]=index;26         array[index]=array[array.size()-1];27         array.pop_back();28         map.erase(val);29         30         return true;31     }32     33     /** Get a random element from the set. */34     int getRandom() {35         if(array.size()>0){36             int index=rand()%array.size();37         38             return array[index];39         }40         return 0;41     }42 private:43     unordered_map
      
        map;44     vector
       
         array;45 };46 47 /**48  * Your RandomizedSet object will be instantiated and called as such:49  * RandomizedSet obj = new RandomizedSet();50  * bool param_1 = obj.insert(val);51  * bool param_2 = obj.remove(val);52  * int param_3 = obj.getRandom();53  */