实现RandomizedSet类：

• RandomizedSet()初始化RandomizedSet对象
• bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。
• bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。
• int getRandom()随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有相同的概率被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为O(1)。

示例：

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

提示：

• -231 <= val <= 231 - 1
• 最多调用insert、remove和getRandom函数2 *105次
• 在调用getRandom方法时，数据结构中至少存在一个元素。

解答：

本题由于时间复杂度要求为O(1)，所以不能只用列表或者只用字典操作，本题是使用加长数组和哈希表查找

1. 题目的目的是什么？（现实意义）

面试官让你实现这个类，绝不只是为了考试。它在现实中的原型就是Redis 的 Set（集合），或者游戏里的“奖池系统”。

• 比如抽卡游戏里，你要往里放奖品（insert）、拿走某个奖品（remove），还要等概率随机抽一个（getRandom）。

• 难点在于，游戏服务器每秒可能要处理几十万次请求，所以必须极其快（O(1) 时间复杂度）。

2. 此题的难点与“核心魔法”（重点）

如果你单独用一个东西，都会踩坑：

• 只用数组（列表）：getRandom非常快（随便挑个下标），但remove很慢，因为删除中间元素需要移动后面所有元素（O(n)）。

• 只用哈希表（字典）：insert和remove极快，但getRandom很慢，因为字典没法随机挑一个下标（键值对是无序的）。

此题的“核心魔法”（也就是难点）在于：把数组和哈希表结合起来，让它们“狼狈为奸”。

• 数组负责存储实际数值，负责提供随机下标。

• 哈希表负责存储数值 -> 下标的映射，负责快速查找。

重点中的重点（删除的“替身术”）：
既然删除数组中间元素很慢（要挪位子），那我们就不删中间！把最后一个元素复制过来，覆盖掉要删除的位置，然后删掉最后一个元素。这样既删除了目标，又保持了数组下标的连续性，而且全程没移动大量数据！

3. 生动形象地解释代码（图书馆管理员的故事）

把self.nums想象成一个书架（数组），把self.indices想象成索引卡片箱（哈希表）。

场景：书架上摆着[10, 20, 30]，索引卡记录着{10: 0, 20: 1, 30: 2}。

插入操作 (insert)：放新书

if val in self.indices: return False # 查卡，发现有这本书，不入库 self.indices[val] = len(self.nums) # 在卡上登记：这本书放在书架最后一格 self.nums.append(val) # 把书放到书架最后一格 return True

比喻：来了本新书40，查卡没有。书架最后一格是下标3，在卡上写40:3，然后把书放上去。

删除操作 (remove)：最精彩的“移形换影”

这是本题的灵魂，我们一步步拆解，假设要删掉书架中间的20（下标 1）：

id = self.indices[val] # 1. 查卡，找到要毁掉的书在位置 1 self.nums[id] = self.nums[-1] # 2. 把最后一本书（30）拿过来，放在位置 1 上。现在书架变成了 [10, 30, 30]（最后一本还是30，不管它） self.indices[self.nums[id]] = id # 3. 修改索引卡！告诉 30：你的新家不在 2 了，现在在 1。卡片变成 {10:0, 20:1, 30:1} self.nums.pop() # 4. 把书架最后一格（那本没人要的重复30）撕掉。书架变成 [10, 30] del self.indices[val] # 5. 把 20 的旧索引卡扔掉。 return True

图解删除魔法：

• 删除前书架：[10, 20, 30]，索引卡：20->1。

• 执行后书架：[10, 30]，索引卡：30->1。

• 你看，我们没碰下标 0 和 1 后面的所有书，只动了最后一本，就完成了删除，而且下标依然连续（0 和 1）！

获取随机 (getRandom)：闭眼抽签

return choice(self.nums) # choice 是 random.choice，随机挑一个下标

比喻：因为书架是连续紧凑的，随便报一个数字（下标），闭眼拿一本，绝对能拿到书。

完整代码：

class RandomizedSet(object): def __init__(self): self.nums=[] self.indice={} def insert(self, val): """ :type val: int :rtype: bool """ if val in self.indice: return False self.indice[val] = len(self.nums) self.nums.append(val) return True def remove(self, val): """ :type val: int :rtype: bool """ if val not in self.indice: return False id = self.indice[val] #记录要删掉的元素的键值 self.nums[id] = self.nums[-1] #把最后一格的元素复制到要删除元素的位置 self.indice[self.nums[id]] = id #告诉刚刚被复制过来的元素，你的键值已经不是原来那个了，现在是“被删除元素”的位置的对应键值 self.nums.pop() #把列表的最后一格直接抛出 del self.indice[val] #把要删除的元素对应的键值索引删掉 return True def getRandom(self): """ :rtype: int """ return choice(self.nums) # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()