LeetCode 380. Insert Delete GetRandom O(1) 题解

LeetCode 380. Insert Delete GetRandom O(1) 题解题目描述实现RandomizedSet 类RandomizedSet() 初始化 RandomizedSet 对象bool insert(int val) 当元素 val 不存在时向集合中插入该项并返回 true 否则返回 false 。bool remove(int val) 当元素 val 存在时从集合中移除该项并返回 true 否则返回 false 。int getRandom() 随机返回现有集合中的一项测试用例保证调用此方法时集合中至少存在一个元素。每个元素应该有相同的概率被返回。你必须实现类的所有函数并满足每个函数的平均时间复杂度为 O(1) 。示例 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解题思路要实现 O(1) 的插入、删除和随机获取需要结合哈希表和数组哈希表存储值到索引的映射支持 O(1) 的查找和删除数组存储所有值支持 O(1) 的随机访问删除操作的关键要删除数组中间的元素时将其与最后一个元素交换然后删除最后一个元素这样避免了移动大量元素保持 O(1) 的时间复杂度代码实现import random class RandomizedSet: def __init__(self): # 哈希表值 - 索引 self.val_to_index {} # 数组存储所有值 self.values [] def insert(self, val): if val in self.val_to_index: return False # 添加到数组末尾 self.val_to_index[val] len(self.values) self.values.append(val) return True def remove(self, val): if val not in self.val_to_index: return False # 获取要删除的值的索引 index self.val_to_index[val] last_val self.values[-1] # 将最后一个元素移到要删除的位置 self.values[index] last_val self.val_to_index[last_val] index # 删除最后一个元素 self.values.pop() del self.val_to_index[val] return True def getRandom(self): return random.choice(self.values)复杂度分析时间复杂度insertO(1)removeO(1)getRandomO(1)空间复杂度O(n)哈希表和数组的空间关键技巧删除操作的优化传统数组删除中间元素需要 O(n) 时间因为要移动后续元素。但我们可以通过以下技巧实现 O(1)找到要删除元素的索引将数组最后一个元素复制到该索引位置更新哈希表中最后一个元素的索引删除数组最后一个元素从哈希表中删除要删除的元素这样只需要常数时间即可完成删除操作。测试案例# 测试案例 1 randomizedSet RandomizedSet() assert randomizedSet.insert(1) True assert randomizedSet.remove(2) False assert randomizedSet.insert(2) True assert randomizedSet.getRandom() in [1, 2] assert randomizedSet.remove(1) True assert randomizedSet.insert(2) False assert randomizedSet.getRandom() 2 # 测试案例 2随机性测试 randomizedSet RandomizedSet() for i in range(10): randomizedSet.insert(i) results [randomizedSet.getRandom() for _ in range(10000)] counts {} for r in results: counts[r] counts.get(r, 0) 1 # 每个数字出现的次数应该接近 1000 for i in range(10): assert 800 counts.get(i, 0) 1200总结本题是数据结构设计中的经典问题考察如何组合不同的数据结构来实现高效的操作。关键点哈希表 数组的组合删除操作的优化与最后一个元素交换随机访问使用 random.choice通过本题可以深入理解如何设计高效的数据结构以及如何在时间和空间之间做出权衡。