当前位置：首页 > news >正文

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

news 2026/7/4 7:22:32

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)

复杂度分析

时间复杂度：
- insert：O(1)
- remove：O(1)
- getRandom：O(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