LeetCode 380. O(1) 时间插入、删除和获取随机元素
题目描述
题意分析
设计一个不允许重复元素的集合，同时支持三个操作：
insert(val)只在值不存在时插入并返回true；remove(val)只在值存在时删除并返回true；getRandom()从当前集合中等概率返回一个值，不删除它。题目保证调用随机接口时集合非空。三个操作都要求平均
O(1)时间，集合不需要保持插入顺序或数值顺序。因此关键是同时支持按值快速定位、快速删除和等概率随机访问，不能只满足其中一部分。
解法：数组 + 哈希表下标
核心思路
[!blue]
数组可以按下标直接访问，适合随机选取一个位置，但直接按值查找或从中间删除都可能需要
O(n)。哈希表可以按值快速定位，却不能直接等概率地取出某个元素。因此组合使用连续数组values和哈希表indexMap：数组保存全部有效值，哈希表保存每个值在数组中的下标。两者始终保持一一对应：
values[indexMap[v]] == v，每个存在的值在数组中恰好占一个位置，数组没有空洞。插入时先判重，未出现过才把当前数组长度记录为新下标，再追加值。删除时先从哈希表取得目标位置。为了避免移动后面所有元素，用数组末尾值覆盖目标位置，同时把末尾值在哈希表中的下标更新为目标下标，最后删除数组末尾并移除目标值的映射。集合没有顺序要求，因此这种换位不会影响操作语义；若目标本来就在末尾，直接弹出即可，不需要搬运和更新另一个值。
随机获取时，只需在
[0, values.size())中均匀抽取一个整数下标。数组紧凑且每个值恰好对应一个位置，所以每个元素被返回的概率都为1 / size。不需要遍历哈希表，也不需要随机抽到无效位置后反复重试。
解题步骤
- 初始化空数组、空下标映射和随机数生成器；Go 使用标准库随机接口。
- 插入时查询
val是否存在：存在返回false，否则记录追加前的数组长度，追加元素并返回true。- 删除时查询
val的下标：不存在返回false；存在则取得末尾下标和末尾值。- 若删除位置不是末尾，将末尾值写入删除位置，并同步更新它的映射。
- 弹出数组末尾，再移除
val的映射，返回true。- 随机操作均匀生成合法下标，读取并返回对应数组元素。
代码实现
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))]
}
复杂度分析
- 时间复杂度：插入、删除和随机获取均为平均
O(1)。哈希查询、更新和删除为平均常数时间；数组尾部追加为均摊常数时间，覆盖、弹尾和按下标访问为常数时间。- 空间复杂度：
O(n)，其中n是当前元素数量。数组保存全部值，哈希表保存对应下标。
关键点总结
[!green]
- 两份结构分工明确：哈希表负责按值定位，连续数组负责随机访问。
- 删除后无需保持顺序，才可以用末尾覆盖把中间删除变成常数次操作。
- 元素位置变化时同步维护下标映射，保持数组和哈希表的一一对应。
- 等概率来自均匀下标与唯一位置的对应关系，而不只是调用了随机函数。
易错点总结
[!yellow]
- 搬动末尾值后忘记更新映射：后续删除该值时会访问已经失效的下标。
- 直接删除数组中间位置：会移动后面的元素，时间变成
O(n)，这些元素的下标映射也会全部过期。- 追加后才记录当前长度为下标：新元素位于追加前的长度处，追加后再记录会偏大一位。
- 允许重复值直接追加：同一个值会对应多个位置，单个下标映射无法表达，也破坏了集合语义。
- 删除时只标记空洞而不收紧数组：随机下标可能命中已删除位置，反复重试不能保证所需的平均时间。
- 随机范围包含数组长度：合法下标上界不包含
size，生成它会越界。- 处理末尾删除时混乱更新同一键：目标和末尾值相同时无需搬运，先区分该情况可避免残留错误映射。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 | 困难 | 同样用数组末尾覆盖被删位置，原题允许重复值，需要值到多个下标的映射。 |
| 710. 黑名单中的随机数 | 困难 | 同样把随机选择转成均匀整数下标抽样，原题用重映射避开黑名单，本题维护动态紧凑数组。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！