实现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下标 1id 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()