LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
题目描述
题意分析
实现允许重复值的集合，支持插入、删除一次出现以及随机取值，三个操作的平均时间都要求为常数。
插入无论值是否已经存在，都要真正新增一次出现；返回值只表示插入前是否没有这个值。删除时只移除一次出现，存在则返回真，不存在则返回假。随机取值不删除元素，同一个值被抽到的概率应与它当前的出现次数成正比。题目保证调用随机查询时集合非空。
解法：动态数组 + 下标集合
核心思路
[!blue]
用动态数组
values紧密保存每一次出现。同一个值可以占多个位置，随机查询时等概率选择一个合法数组下标即可：某值占据多少个位置，就有多少份被抽中的机会，自然得到按出现次数加权的概率。还需要从指定值迅速找到它的一次出现。
indices保存每个值对应的全部数组下标。插入时，将新下标登记到对应记录，并把值追加到数组尾部；重复值同样追加，只是返回false。删除时，从记录中取一个下标removeIndex，无需在线性数组中查找。直接删除数组中间元素会移动后面整段。由于题目不要求保存顺序，可以用最后一个元素补到被删位置，再截短数组。这样只改动一个存活元素的位置，同时把它在
indices中登记的旧尾下标改为补洞下标即可。Java 用
LinkedHashSet保存每个值的下标。它既支持平均常数时间的下标增删，也能沿链直接取得首项。普通HashSet每次新建迭代器取第一项，可能先扫描许多空桶，不能据此保证删除操作的平均常数成本。Go 用每个值的位置列表保存下标，直接取列表末项作为待删位置。为避免移动尾元素时在线性列表中寻找旧下标，另用
slots[i]记录values[i]这次出现在自己位置列表中的槽位。于是数组尾项的旧记录可以通过slots[lastIndex]直接定位，改成removeIndex；移动后的数组位置也接收这个槽位编号。更新时先移除目标出现的记录，再修正被移动尾项的记录，最后截短数组并清除空的值记录。尾项可能与待删值相同，此时修改的是同一份记录。Go 已先保存尾项槽位；若两者物理位置不同，尾项槽位就不是刚弹掉的列表末槽，仍然有效。Java 同样先删目标下标，再把旧尾下标换成新位置，完成后才判断集合是否为空。
若待删位置已经是数组尾部，则不用补洞，也不需要改动其他出现的映射。上述对应关系保持后，后续查找、删除和随机访问都可以继续直接定位。
解题步骤
- 插入时检查该值此前是否存在，登记新的数组下标，并追加这一次出现；Go 同步记录它在位置列表中的槽位。
- 删除时先查找对应记录，不存在则返回假。
- 取出待删下标，保存数组尾项的值和位置元数据，再移除目标下标记录。
- 待删位置不是尾部时，用尾项补洞，并同步更新尾值对应的下标记录；Go 同步移动槽位编号。
- 截短数组，删除已经为空的值记录，返回真。
- 随机查询时在
[0, values.size())内等概率选取下标并返回对应值。
代码实现
class RandomizedCollection {
private final List<Integer> values = new ArrayList<>();
private final Map<Integer, Set<Integer>> indices = new HashMap<>();
public boolean insert(int val) {
Set<Integer> set = indices.computeIfAbsent(val, key -> new LinkedHashSet<>());
// 重复值仍插入，返回值只表示此前是否存在
boolean first = set.isEmpty();
set.add(values.size());
values.add(val);
return first;
}
public boolean remove(int val) {
Set<Integer> removeSet = indices.get(val);
if (removeSet == null) {
return false;
}
int removeIndex = removeSet.iterator().next();
int lastIndex = values.size() - 1;
int lastValue = values.get(lastIndex);
// 先移除目标下标，再修正可能属于同一集合的尾项
removeSet.remove(removeIndex);
if (removeIndex != lastIndex) {
values.set(removeIndex, lastValue);
Set<Integer> lastSet = indices.get(lastValue);
lastSet.remove(lastIndex);
lastSet.add(removeIndex);
}
values.remove(lastIndex);
// 完成补洞后，才判断该值是否已无剩余出现
if (removeSet.isEmpty()) {
indices.remove(val);
}
return true;
}
public int getRandom() {
int index = ThreadLocalRandom.current().nextInt(values.size());
return values.get(index);
}
}
import "math/rand"
type RandomizedCollection struct {
values []int
slots []int
indices map[int][]int
}
func Constructor() RandomizedCollection {
return RandomizedCollection{indices: make(map[int][]int)}
}
func (this *RandomizedCollection) Insert(val int) bool {
positions := this.indices[val]
first := len(positions) == 0
this.indices[val] = append(positions, len(this.values))
this.slots = append(this.slots, len(positions))
this.values = append(this.values, val)
return first
}
func (this *RandomizedCollection) Remove(val int) bool {
positions, exists := this.indices[val]
if !exists {
return false
}
removeIndex := positions[len(positions)-1]
lastIndex := len(this.values) - 1
lastValue := this.values[lastIndex]
lastSlot := this.slots[lastIndex]
this.indices[val] = positions[:len(positions)-1]
if removeIndex != lastIndex {
this.values[removeIndex] = lastValue
this.slots[removeIndex] = lastSlot
this.indices[lastValue][lastSlot] = removeIndex
}
this.values = this.values[:lastIndex]
this.slots = this.slots[:lastIndex]
if len(this.indices[val]) == 0 {
delete(this.indices, val)
}
return true
}
func (this *RandomizedCollection) GetRandom() int {
return this.values[rand.Intn(len(this.values))]
}
复杂度分析
- 时间复杂度：插入和删除为期望、均摊 $O(1)$，哈希表定位和记录更新为期望常数，动态数组追加为均摊常数。Java 直接取链式集合首项，Go 直接取列表末项并通过反向槽位更新，都不扫描记录。随机查询为 $O(1)$。
- 空间复杂度：$O(n)$，
n为插入操作总次数。每次插入至多增加常数条数组与下标记录；删除会减少有效记录，但动态容器可能保留已经分配的容量。
关键点总结
[!green]
- 随机等概率的是每次出现对应的数组位置，不是不同数值的种类。
- 尾项补洞把数组删除化为常数次改写，但数组位置与反向记录必须一起更新。
- 找到某个值之后，取出和修改它的一次出现也必须能直接定位，不能隐藏一次线性扫描。
易错点总结
[!yellow]
- 看到插入返回假，就不把重复值加入数组，混淆了返回语义与实际操作。
- 为每个值只记录一个下标，无法保留或删除其余重复出现。
- 补洞后没有改写尾值的下标记录，下一次删除会访问已经失效的位置。
- 默认尾值一定不同于待删值，会在同一份记录上按错误顺序增删，破坏仍存活的出现。
- Go 只更新位置列表、没有把尾项槽位写到补洞位置，后续移动会定位到错误记录。
- 从不同值的键集合中等概率抽样，会丢掉重复次数带来的概率权重。
- 为了删除中间位置而移动数组后面的全部元素，结果虽然可能正确，却不满足平均常数时间要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 允许重复后，值不能只映射到一个下标，删除时要维护每个值的下标集合。 |