原题地址（中等）

方法1—哈希表

思路

这题与381题几乎一致，只不过比381题稍微简单点，其实应该先做这道题，再做380题的。
常数时间内插入删除都好说，一个哈希map就可以搞定，但是随机返回其中一项也要在O（1）时间内，这就不好办了。

理一下随机返回的思路：随机返回的话，就要先获得一个小于等于数组长度的随机数，然后直接按照下标随机存取。所以说元素必须要用一个vector来存取，并且vector里面的元素没有顺序要求，怎么放置都可以，因为这个vector只用来随机返回一个元素。

而对于插入删除，则用哈希hash实现。

所以难点就是插入删除的时候，怎么保证哈希hash和vector都能够同步的进行。
插入的时候好说，hash直接插入，vector直接push_back就好。
那么删除呢？hash也好说，可以直接删除，可是vector该咋办？ 所以说我们这个哈希map，值是元素在vector中的索引 ，这样在删除之前，先从哈希map中拿到下标索引，然后可以将hashmap成功删除。
至于vector呢？ 我们现在有了要删除元素的下标，直接将最后一个元素和该元素互换，然后删除最后一个元素就好啦。
具体做法是：直接用最后一个元素覆盖掉要删除的元素，然后vector执行pop_back操作。注意，别忘了把最后一个元素在hash map中的值改为要删除元素的索引值。

代码

  1. class RandomizedSet {
  2. public:
  3.     unordered_map<int, int> hash;
  4.     vector<int> nums;
  5.     /** Initialize your data structure here. */
  6.     RandomizedSet() {
  8.     }
  10.     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  11.     bool insert(int val) {
  12.         if(hash.find(val) != hash.end())   return false;
  13.         nums.push_back(val);
  14.         hash[val] = nums.size()-1;
  15.         return true;        
  16.     }
  18.     /** Removes a value from the set. Returns true if the set contained the specified element. */
  19.     bool remove(int val) {
  20.         //  判断是否存在val
  21.         if(hash.find(val) == hash.end())  return false;
  22.         int idx = hash[val];   //获得要删元素的下标
  23.         hash.erase(val);   // hash中删除
  24.         int tmp = nums.back();  
  25.         //  这里的if else是处理要删除的元素就是最后一个元素的情况
  26.         if(nums[idx] == tmp)
  27.             nums.pop_back();
  28.         else{
  29.             nums[idx] = tmp;
  30.             hash[tmp] = idx;
  31.             nums.pop_back();
  32.         }
  33.         return true;
  34.     }
  36.     /** Get a random element from the set. */
  37.     int getRandom() {
  38.         return nums[rand() % nums.size()];
  39.     }
  40. };

时空复杂度