原题地址（困难）

方法1—哈希表

思路

这题想了半个多小时，还是没做对。。。。

挺难得。

主要还是对哈希表的运用和操作不熟练。这个题随机数要想实现O（1），就只能是用vector存数，然后下标查找；那么删除就做不到O（1）。所以为了删除能做到O（1），还要用一个哈希表来存储每个元素的各个下标（因为允许重复嘛，所以一个元素可能有多个下标）

难点就在于删除函数。怎么实现O（1）呢？
在哈希表中找到要删除元素的一个下标，然后在vector中将这个下标的元素与最后一个元素互换，然后删掉最后一个元素。
**
具体实现时还是有坑的。比如说操作“插入1，删除1”。我就摔在这里了。。。
还有，unordered_set中即使没有元素，erase也不会报错，同时返回0，代表没元素可删！！

然后直接看了官方题解。

代码

  1. class RandomizedCollection {
  2. public:
  3.     unordered_map<int, unordered_set<int>> idx;
  4.     vector<int> nums;
  6.     /** Initialize your data structure here. */
  7.     RandomizedCollection() {
  9.     }
  11.     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
  12.     bool insert(int val) {
  13.         nums.push_back(val);
  14.         idx[val].insert(nums.size() - 1);
  15.         return idx[val].size() == 1;
  16.     }
  18.     /** Removes a value from the collection. Returns true if the collection contained the specified element. */
  19.     bool remove(int val) {
  20.         if (idx.find(val) == idx.end()) {
  21.             return false;
  22.         }
  23.         int i = *(idx[val].begin());
  24.         nums[i] = nums.back();
  25.         idx[val].erase(i);
  26.         idx[nums[i]].erase(nums.size() - 1);
  27.         if (i < nums.size() - 1) {
  28.             idx[nums[i]].insert(i);
  29.         }
  30.         if (idx[val].size() == 0) {
  31.             idx.erase(val);
  32.         }
  33.         nums.pop_back();
  34.         return true;
  35.     }
  37.     /** Get a random element from the collection. */
  38.     int getRandom() {
  39.         return nums[rand() % nums.size()];
  40.     }
  41. };
  43. 作者：LeetCode-Solution
  44. 链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed/solution/o1-shi-jian-cha-ru-shan-chu-he-huo-qu-sui-ji-yua-5/
  45. 来源：力扣（LeetCode）
  46. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时空复杂度