设计一个数据结构实现在平均 O(1) 的复杂度下执行以下所有的操作。

• insert(val): 如果这个元素不在set中，则插入。

• remove(val): 如果这个元素在set中，则从set中移除。

• getRandom: 随机从set中返回一个元素。每一个元素返回的可能性必须相同。

 

样例

// 初始化空集setRandomizedSet randomSet = new RandomizedSet();// 1插入set中。返回正确因为1被成功插入randomSet.insert(1);// 返回错误因为2不在set中randomSet.remove(2);// 2插入set中，返回正确，set现在有[1,2]。randomSet.insert(2);// getRandom 应该随机的返回1或2。randomSet.getRandom();// 从set中移除1，返回正确。set现在有[2]。randomSet.remove(1);// 2已经在set中，返回错误。randomSet.insert(2);// 因为2是set中唯一的数字，所以getRandom总是返回2。randomSet.getRandom(); 其实就是一个数据结构选型的问题 光用一个vector是不够的，因为每次插入删除都要进行搜索，O（n） 注意到不能有复数个相同的元素，很容易想到基于红黑树的map，或者比较新的c++11中的unordered_map unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，而map会。 这两个都能用，甚至在这一题中unordered_map更合适，毕竟key排序在这里无关紧要 那么现在有一个vector来存储数据，一个map用来当字典索引，接下来怎么做? 对于插入，先在map里面用count查有没有这个元素，有直接返回，没有就插入vector并在map添加相应tiaomu 对于删除，还是查map里面有没有这个元素，没有直接返回，有的话： 1、将vector最后一个值覆盖到要删除值，nums[dict[val]] = nums[nums.size()-1];  这时候vector中有两个最后一个值 2、将map中最后一个值的位置设成要删除的值的位置，dict[nums[nums.size()-1]]=dict[val]; 这时候map中两个key都指向同一个vector位置 3、用pop_back()删掉最后一个vector值，用erase删掉map中需要删除的条目 随机还是很简单的

1 class RandomizedSet { 2 private: 3     vector
      
        nums; 4     map
       
         dict; 5 public: 6     RandomizedSet() { 7         // do intialization if necessary 8     } 9 10     /*11      * @param val: a value to the set12      * @return: true if the set did not already contain the specified element or false13      */14     bool insert(int val) {15         // write your code here16         if(dict.count(val)){17             return false;18         }19         nums.push_back(val);20         dict[val]=nums.size()-1;21     }22 23     /*24      * @param val: a value from the set25      * @return: true if the set contained the specified element or false26      */27     bool remove(int val) {28         // write your code here29         if(!dict.count(val)){30             return false;31         }32         33         nums[dict[val]] = nums[nums.size()-1];  34         dict[nums[nums.size()-1]]=dict[val];35         36         nums.pop_back();  37         dict.erase(val);  38         return true;  39     }40 41     /*42      * @return: Get a random element from the set43      */44     int getRandom() {45         // write your code here46         return nums[rand() % nums.size()];47     }48 };