LeetCode 380. O(1) 时间插入、删除和获取随机元素
目录
题目描述
题意分析
这是一道设计题，要求实现一个不含重复元素的集合，支持三个操作：
insert(val)在元素不存在时插入并返回真、已存在时不插入并返回假；remove(val)在元素存在时删除并返回真、不存在时返回假；getRandom()从当前集合中返回一个元素。约束里有两句话是全部难度的来源。第一句是三个操作都必须达到平均 $O(1)$ 的时间复杂度——注意是三个都要，不是挑其中两个；很多结构能做到其中两个，卡住的永远是第三个。第二句是
getRandom必须保证每个当前存在的元素被返回的概率相同，也就是等概率均匀采样，不能出现「某些元素更容易被抽到」的偏置。还有两个容易被忽略的信号。其一，集合不含重复元素，插入和删除都要先做存在性判断并把判断结果作为返回值，这意味着必须有一个能 $O(1)$ 回答「在不在」的组件。其二，题目保证调用
getRandom时集合中至少有一个元素，所以不需要为空集合设计返回值，但内部结构仍要保证「元素个数」这个量随时可读。边界方面，需要考虑删除的恰好是最近一次插入的元素、删除后集合变空、以及删除后再插入同一个值这几种序列，它们是检验实现是否自洽的最小用例集。
解法：数组 + 哈希表下标
核心思路
单独使用哈希表可以平均 $O(1)$ 判存和删除，却不能按下标等概率取元素；单独使用动态数组可以 $O(1)$ 随机访问，但查找和删除中间元素是 $O(n)$。因此组合两种结构：
- 动态数组
values保存当前所有元素，负责随机访问。- 哈希表
indexMap保存「元素值到数组下标」，负责判存和定位。插入只需把新值追加到数组末尾并记录下标。删除是本题关键：集合不要求顺序，可以把数组最后一个元素搬到待删除位置，再弹出末尾，从而避免移动后续元素；若确实发生搬动，还要同步更新尾元素在哈希表中的下标。
始终维护不变量：哈希表的键与数组元素完全一致，并且对任意元素
v都有values[indexMap[v]] == v。插入和「尾元素补位」都同步更新两份数据，因此不变量持续成立。
getRandom在连续下标区间 $[0,n)$ 上均匀取一个下标。数组无空洞且每个元素只占一个位置，所以每个元素被选中的概率都是 $1/n$。
解题步骤
insert(val)：若哈希表已有val，返回false；否则记录当前数组长度为其下标，再追加到数组末尾。remove(val)：从哈希表查询待删除下标，不存在则返回false。- 取得数组尾元素；若删除位置不是末尾，就用尾元素覆盖该位置，并更新尾元素的下标映射。
- 弹出数组末尾，删除
val的映射，返回true。getRandom()：生成[0, values.size())内的均匀随机下标并返回对应元素。例如数组为
[1, 2, 3]、映射为{1:0, 2:1, 3:2}。删除1时，用尾元素3覆盖下标0，更新3 -> 0后弹尾，最终数组为[3, 2]，两份结构仍保持一致。
代码实现
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
class RandomizedSet {
private final List<Integer> values = new ArrayList<>();
private final Map<Integer, Integer> indexMap = new HashMap<>();
private final Random random = new Random();
public boolean insert(int val) {
if (indexMap.containsKey(val)) {
return false;
}
indexMap.put(val, values.size());
values.add(val);
return true;
}
public boolean remove(int val) {
Integer index = indexMap.get(val);
if (index == null) {
return false;
}
int lastIndex = values.size() - 1;
int lastValue = values.get(lastIndex);
if (index != lastIndex) {
values.set(index, lastValue);
indexMap.put(lastValue, index);
}
values.remove(lastIndex);
indexMap.remove(val);
return true;
}
public int getRandom() {
return values.get(random.nextInt(values.size()));
}
}
import "math/rand"
type RandomizedSet struct {
values []int
indexMap map[int]int
}
func Constructor() RandomizedSet {
return RandomizedSet{indexMap: make(map[int]int)}
}
func (this *RandomizedSet) Insert(val int) bool {
if _, exists := this.indexMap[val]; exists {
return false
}
this.indexMap[val] = len(this.values)
this.values = append(this.values, val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
index, exists := this.indexMap[val]
if !exists {
return false
}
lastIndex := len(this.values) - 1
lastValue := this.values[lastIndex]
if index != lastIndex {
this.values[index] = lastValue
this.indexMap[lastValue] = index
}
this.values = this.values[:lastIndex]
delete(this.indexMap, val)
return true
}
func (this *RandomizedSet) GetRandom() int {
return this.values[rand.Intn(len(this.values))]
}
复杂度分析
- 时间复杂度：
insert、remove和getRandom均为平均 $O(1)$。动态数组尾部追加为均摊 $O(1)$，哈希表操作为平均 $O(1)$。- 空间复杂度：$O(n)$。数组与哈希表各保存 $n$ 个元素或映射。
关键点总结
- 数组提供连续下标和均匀随机访问，哈希表补足按值定位能力。
- $O(1)$ 删除成立的前提是集合无序，因此可以用尾元素补洞。
- 数组中元素位置变化时，必须同步更新哈希表中的下标。
- 连续且无空洞的数组使「均匀随机下标」自然等价于「均匀随机元素」。
- 单独判断删除末尾的情况，可避免先写回再删除同一映射造成顺序错误。
易错点总结
- 用尾元素覆盖删除位置后，忘记更新尾元素的下标映射。
- 使用数组的中间删除接口，导致后续元素整体移动，复杂度退化为 $O(n)$，且大量映射失效。
- 插入后才记录
values.size()，会把新元素下标多算一位；应在追加前记录长度。- 删除尾元素时仍无条件写回映射，若更新与删除顺序不当会留下幽灵记录。
- 数组保留空洞或墓碑，
getRandom可能选到已删除位置，无法保证 $O(1)$。- 随机接口上界使用闭区间，可能生成下标
n并越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 | 困难 | 允许重复，哈希表的值要从单个下标升级成下标集合 |
| 146. LRU 缓存 | 中等 | 同样是哈希表配合另一结构，但补的是顺序而非随机访问 |
| 384. 打乱数组 | 中等 | 考等概率洗牌，随机性要求从单点采样升级到整体排列 |
| 398. 随机数索引 | 中等 | 在重复值中等概率选一个下标，可练蓄水池抽样 |
| 528. 按权重随机选择 | 中等 | 采样概率不再均匀，需要前缀和加二分定位 |
| 705. 设计哈希集合 | 简单 | 要求自己实现哈希表本身，而不是直接调用现成容器 |
| LCR 030. O(1) 时间插入、删除和获取随机元素 | 中等 | 与本题同构，可用于复述数组加哈希表的组合套路 |