剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

思路——————哈希表 + 数组
由于题目要求删除和插入的时间复杂度为 O(1)，能够满足要求的只有哈希表，显然此处需要使用哈希表。
但是使用哈希表无法等概率返回其中的每个数值。若这些数值是保存在数组内，则可以轻松解决。但若只使用数组，那么删除和插入一个值时，都需遍历一遍数组找到数值对应的下标，则会使时间复杂度为 O(n)。
故可将哈希表和数组结合，数组内存数值实现 getRandom，哈希内存数值和下标的映射实现 insert 和 remove 的索引查找的时间复杂度为 O(1)，之后在数组内操作数值的插入和删除。具体来看操作就是：
1. 插入
每次添加新数值时，先使用哈希表判断该数值是否存在，存在则直接返回false。不存在则进行插入操作，只要将该数值添加到数组尾部即可，并将该数值和其下标的映射存入哈希表。
2. 删除
删除同样需使用哈希表判断是否存在，若不存在则返回false。存在则进行删除操作，在哈希表中删除时间复杂度为 O(1)，但是在数值中删除比较麻烦。若只是直接删除，则为了保证数组内存连续性需将删除数值后面的数值均前移一位，时间复杂度为 O(n)。比较好的处理方式是，用数组的最后一个数值去填充需要删除的数值的内存，其他数值在数组中的位置保持不变，并将这个拿来填充的数值的下标更新即可，最后只要删除数组最后一个数值，同样可以保证时间复杂度为 O(1)。
3. 随机返回
只要随机生成数组下标范围内一个随机下标值，返回该数组下标内的数值即可。
简而言之就是使用哈希表的值来存储数组的下标，使用哈希表来完成复杂度为1的插入和删除操作，使用数组的特点来完成随机返回操作

  1. class RandomizedSet {
  2. private:
  3.     unordered_map<int, int> numToLocation;
  4.     vector<int> nums;
  5. public:
  6.     RandomizedSet() {
  8.     }
  10.     bool insert(int val) {
  11.         if (numToLocation.count(val)) {
  12.             return false;
  13.         }
  14.         numToLocation[val] = nums.size();
  15.         nums.push_back(val);
  16.         return true;
  17.     }
  19.     bool remove(int val) {
  20.         if (!numToLocation.count(val)) {
  21.             return false;
  22.         }    
  23.         int location = numToLocation[val];
  24.         numToLocation[nums.back()] = location;
  25.         numToLocation.erase(val);
  26.         nums[location] = nums.back();
  27.         nums.pop_back();
  28.         return true;
  29.     }
  31.     int getRandom() {
  32.         return nums[rand() % nums.size()];
  33.     }
  34. };