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

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

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：
insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

示例 :

输入: inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
RandomizedSet randomSet = new RandomizedSet();  // 初始化一个空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入ve(2); // 返回 false，表示集合中不存在 2 randomSet.insert(2); // 向集合中插入 2 返回 true ，集合现在包含 [1,2] Random(); // getRandom 应随机返回 1 或 ve(1); // 从集合中移除 1 返回 true 。集合现在包含 [2] randomSet.insert(2); // 2 已在集合中，所以返回 Random(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 

提示：

-231 <= val <= 231 - 1
最多进行 2 * 105 次 insert ， remove 和 getRandom 方法调用
当调用 getRandom 方法时，集合中至少有一个元素

有一说一，这道题刚开始确实没什么思路，看到题意以后有点蒙，后来瞅了眼评论区，知道了题目的难点在插入删除操作上，能够做到时间复杂度为 O ( 1 ) O(1) O(1)。其实如果没有这个要求，那直接建个hash表就行了，但是hash表无法做到random返回数值，以为hash表是树结构，只能遍历，无法随机读取，而随机读取的性质，很明显就是要有个数组来实现，因此本题需要简历一个hash一个数组。

1. 插入
   每次添加新数值时，先使用哈希表判断该数值是否存在，存在则直接返回false。不存在则进行插入操作，只要将该数值添加到数组尾部即可，并将该数值和其下标的映射存入哈希表。

2. 删除
   删除同样需使用哈希表判断是否存在，若不存在则返回false。存在则进行删除操作，在哈希表中删除时间复杂度为 O(1)，但是在数值中删除比较麻烦。若只是直接删除，则为了保证数组内存连续性需将删除数值后面的数值均前移一位，时间复杂度为 O(n)。比较好的处理方式是，用数组的最后一个数值去填充需要删除的数值的内存，其他数值在数组中的位置保持不变，并将这个拿来填充的数值的下标更新即可，最后只要删除数组最后一个数值，同样可以保证时间复杂度为 O(1)。

3. 随机返回
   只要随机生成数组下标范围内一个随机下标值，返回该数组下标内的数值即可。

class RandomizedSet {
private:unordered_map<int,int> hash;vector<int> arr;
public:/** Initialize your data structure here. */RandomizedSet() {}/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */bool insert(int val) {unt(val)){return false;}else{hash[val] = arr.size();place_back(val);return true;}}/** Removes a value from the set. Returns true if the set contained the specified element. */bool remove(int val) {unt(val)){arr[hash[val]] = arr.back();hash[arr.back()] = hash[val];arr.pop_back();ase(val);return true;}else{return false;}}/** Get a random element from the set. */int getRandom() {return arr[rand()%arr.size()];}
};/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet* obj = new RandomizedSet();* bool param_1 = obj->insert(val);* bool param_2 = obj->remove(val);* int param_3 = obj->getRandom();*/