LeetCode LCR 030. O(1) 时间插入、删除和获取随机元素
目录
题目描述
题意分析
设计一个集合类，支持三个操作：
insert(val)插入并返回是否真的插入了（已存在则返回假）、remove(val)删除并返回是否真的删除了（不存在则返回假）、getRandom()等概率地返回集合中任意一个元素。三个操作的平均时间复杂度都要求 $O(1)$。这条复杂度要求把题目变成一道「数据结构设计」题而不是算法题。逐个拆解可以看到三种需求彼此冲突。
「判断是否已存在」和「按值删除」天然指向哈希结构：只有哈希才能在常数时间里回答「这个值在不在」。
「等概率随机取一个元素」则指向连续数组：必须能用一次随机下标直接命中某个元素。哈希表的桶是稀疏的，随机挑一个桶再线性找非空位置，概率既不均匀、时间也不是常数。
冲突就在这里：数组能随机取，但按值删除需要先找到位置，而且删中间元素还要搬动后面所有元素，都是 $O(n)$；哈希表能按值定位，却不能随机取。所以单一结构无法同时满足，必须组合两种结构并让它们保持同步。
边界还要注意：
getRandom只在集合非空时被调用（题目保证），删除最后一个元素、删除唯一元素、以及删除的恰好是数组末尾元素这几种情形，代码要能走同一条路径。
解法：哈希表统计状态
核心思路
先看两种单结构方案各自的瓶颈。只用哈希集合：
insert与remove都是 $O(1)$，但getRandom无法在常数时间内等概率取值。只用数组：getRandom是 $O(1)$，但insert要先查重、remove要先定位再搬移，都是 $O(n)$。两者的短板正好互补，于是同时维护两份结构：数组
nums存放全部元素，保证可随机下标访问；哈希表indexMap记录「元素值 → 它在数组中的下标」，保证可按值定位。核心不变量是：
indexMap的键集合恰好等于nums中元素的集合，且对每个v都有nums[indexMap[v]] == v。三个操作都必须在返回前把这条不变量恢复好。
insert很直接：查哈希判重，不存在就把值追加到数组末尾，并记下它的下标。追加是数组唯一的 $O(1)$ 写入位置。
remove是全题的关键。删数组中间的元素之所以贵，是因为要把后面的元素整体前移以保持连续。但这里存的是集合，元素顺序毫无意义，所以完全不必保持原有次序——把数组末尾的元素搬到被删位置上，再删掉末尾，一次覆盖加一次尾删，全是 $O(1)$，而且数组依然连续。搬动之后别忘了把「搬过来那个元素的新下标」写回哈希表，这正是维持不变量的那一步。
getRandom就是在[0, size)里取一个随机下标返回对应元素。因为数组始终连续无空洞，每个元素被选中的概率都是 $1/size$，天然等概率。
解题步骤
- 构造函数：初始化空数组、空哈希表和随机数发生器。随机数发生器建一次复用，不要每次调用
getRandom都新建，那样在同一毫秒内可能产生相同种子导致分布退化。insert先查后写：if (indexMap.containsKey(val)) return false;。查重必须在写入之前，否则会把已有元素重复追加进数组，getRandom的概率分布立刻失衡。insert记录下标再追加：indexMap.put(val, nums.size())用的是追加之前的长度，也就是新元素落位后的下标；如果先nums.add(val)再取nums.size()，下标会多 1，指向数组外。remove先取下标：idx = indexMap.get(val)，不存在直接返回假。remove用末尾元素覆盖：last = nums.get(nums.size() - 1); nums.set(idx, last); indexMap.put(last, idx);。三句是一个整体：搬了元素就必须同步改它的下标记录，否则哈希表会指向一个已经不属于它的位置。remove再删末尾并清哈希：nums.remove(nums.size() - 1); indexMap.remove(val);。顺序很讲究——indexMap.put(last, idx)必须排在indexMap.remove(val)之前，因为删的恰好是末尾元素时last就等于val，先删后写会把它又加回来。getRandom取随机下标：nums.get(random.nextInt(nums.size()))，范围是[0, size)，正好覆盖全部合法下标。走一遍操作序列。初始
nums = []、indexMap = {}。
insert(1)：哈希无1，记indexMap = {1:0}，nums = [1]，返回真。remove(2)：哈希无2，返回假，两个结构都不动。insert(2)：记indexMap = {1:0, 2:1}，nums = [1, 2]，返回真。此时getRandom以各 1/2 的概率返回 1 或 2。
remove(1)：取到idx = 0；末尾元素last = 2；把nums[0]覆盖成2，数组暂时是[2, 2]；写回indexMap[2] = 0；删掉末尾得nums = [2]；再删indexMap[1]，得indexMap = {2:0}。不变量成立：nums[indexMap[2]] == nums[0] == 2。返回真。
insert(2)：哈希里已有2，返回假，不做任何改动。getRandom：数组只有一个元素，必定返回 2。再看「删的正好是末尾」这个容易出错的情形：
nums = [1, 2]、indexMap = {1:0, 2:1}时执行remove(2)。idx = 1，last = nums[1] = 2，nums.set(1, 2)是一次无害的自我覆盖；indexMap.put(2, 1)把2的下标又写成1（值没变）；删末尾得nums = [1]；最后indexMap.remove(2)把它清掉，得indexMap = {1:0}。结果正确——正是因为把remove(val)放在最后，才没有出现「先删掉再被put加回来」的残留。
代码实现
class RandomizedSet {
private final List<Integer> nums;
private final Map<Integer, Integer> indexMap;
private final Random random;
public RandomizedSet() {
nums = new ArrayList<>();
indexMap = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
if (indexMap.containsKey(val)) {
return false;
}
// 取的是追加之前的长度，正好是新元素落位后的下标。
indexMap.put(val, nums.size());
nums.add(val);
return true;
}
public boolean remove(int val) {
if (!indexMap.containsKey(val)) {
return false;
}
int idx = indexMap.get(val);
// 用末尾元素覆盖待删位置，把 O(n) 的搬移变成 O(1) 的覆盖。
int last = nums.get(nums.size() - 1);
nums.set(idx, last);
indexMap.put(last, idx);
nums.remove(nums.size() - 1);
// 必须最后删，否则删的恰好是末尾元素时会被上一行加回来。
indexMap.remove(val);
return true;
}
public int getRandom() {
return nums.get(random.nextInt(nums.size()));
}
}
type RandomizedSet struct {
nums []int
indexMap map[int]int
}
func Constructor() RandomizedSet {
return RandomizedSet{
nums: []int{},
indexMap: make(map[int]int),
}
}
func (rs *RandomizedSet) Insert(val int) bool {
if _, ok := rs.indexMap[val]; ok {
return false
}
// 取的是追加之前的长度，正好是新元素落位后的下标。
rs.indexMap[val] = len(rs.nums)
rs.nums = append(rs.nums, val)
return true
}
func (rs *RandomizedSet) Remove(val int) bool {
idx, ok := rs.indexMap[val]
if !ok {
return false
}
// 用末尾元素覆盖待删位置，把 O(n) 的搬移变成 O(1) 的覆盖。
last := rs.nums[len(rs.nums)-1]
rs.nums[idx] = last
rs.indexMap[last] = idx
rs.nums = rs.nums[:len(rs.nums)-1]
// 必须最后删，否则删的恰好是末尾元素时会被上一行加回来。
delete(rs.indexMap, val)
return true
}
func (rs *RandomizedSet) GetRandom() int {
return rs.nums[rand.Intn(len(rs.nums))]
}
复杂度分析
- 时间复杂度：三个操作均为平均 $O(1)$。
insert是一次哈希查询加一次数组追加（动态数组扩容摊还后仍是常数）；remove是一次哈希查询、一次数组覆盖、一次尾删和两次哈希写；getRandom是一次随机数生成加一次下标访问。哈希冲突极端时会退化，所以严格说是平均而非最坏。- 空间复杂度：$O(n)$，
n为集合中元素个数。数组和哈希表各存一份全部元素，是两倍常数的 $O(n)$，这是「同时具备随机访问和按值定位」必须付出的代价。
关键点总结
- 单一数据结构满足不了全部操作时，就把互补的两种叠起来用，并明确写出连接它们的不变量——本题即「哈希的键集等于数组元素集，且
nums[indexMap[v]] == v」。- 「集合无序」是本题最关键的题意红利：正因为顺序无意义，删除才可以用末尾覆盖代替整体前移，把 $O(n)$ 打到 $O(1)$。看到「集合」「无序」这类字眼要立刻想到这个技巧。
- 等概率随机要求底层存储连续无空洞，任何会留下墓碑或空位的删除方案都会破坏
getRandom的均匀性。- 搬动元素后必须同步更新它的索引记录，涉及两份结构的设计题里，「谁动了就更新谁的映射」是最容易漏的一环。
- 删除时哈希写与哈希删的先后顺序，在「删的是末尾元素」这一情形下会产生实质差异，这类自我覆盖的退化情形要单独代入验证。
- 面试视角：先说清楚「哈希不能随机、数组不能快删」这对矛盾，再引出末尾覆盖的技巧，最后主动补一句「如果要求支持重复元素，值到下标的映射要换成值到下标集合的映射」，这正是 381 题的进阶方向，能体现你想到了扩展性。
易错点总结
insert先追加再记录下标：写成nums.add(val); indexMap.put(val, nums.size());，插入1后记录的下标是 1 而不是 0，之后remove(1)会读到越界或错误位置。remove中先indexMap.remove(val)再indexMap.put(last, idx)：删除末尾元素时last == val，被删掉的键又被写回，nums = [1, 2]上remove(2)后哈希里仍残留2，后续insert(2)会错误地返回假。- 搬完元素忘记
indexMap.put(last, idx)：nums = [1, 2]执行remove(1)后哈希里2的下标仍是 1，而数组只剩一个元素，再remove(2)会取到越界下标。remove用nums.remove(Integer.valueOf(val))按值删除：Java 的按值删除是 $O(n)$ 线性查找，复杂度要求直接不满足，元素多时会超时。- 删除时把中间元素直接
nums.remove(idx)：后续所有元素下标整体前移，而哈希表里记录的还是旧下标，nums = [1, 2, 3]删掉1后indexMap[3]仍是 2，指向越界位置。insert不查重就追加：连续insert(1)两次会让数组变成[1, 1]，getRandom返回 1 的概率变成 100%，分布错误且返回值也不符合题意。- 每次
getRandom都new Random()：短时间内连续调用可能得到相同种子，返回值高度相关，随机性检验会失败。getRandom写成random.nextInt(nums.size() - 1)：范围变成[0, size-1)，最后一个元素永远取不到，nums = [1, 2]时只会返回 1。- Go 里删末尾写成
rs.nums = rs.nums[:idx]：截断位置错成被删下标，nums = [1, 2, 3]上remove(1)会一次丢掉两个元素。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 与本题同题，可直接套用数组加哈希的组合 |
| 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 | 困难 | 允许重复后映射值要换成下标集合，删除时还要处理集合内任取一个下标 |
| 528. 按权重随机选择 | 中等 | 概率不再均匀，要用前缀和加二分把权重转成区间长度 |
| 384. 打乱数组 | 中等 | 考等概率排列而非等概率单点，核心是洗牌算法的正确性证明 |
| 710. 黑名单中的随机数 | 困难 | 同样用映射把稀疏空间压成连续区间，只是被压掉的是黑名单而非删除项 |
| 432. 全 O(1) 的数据结构 | 困难 | 同样要求全部操作 $O(1)$，但需要哈希配合双向链表来维护计数的有序性 |