题目重点：数组存每次出现，value→索引集合支持删指定值，随机下标支持按 occurrence 均匀删除。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版允许重复值，`remove(value)` 删除任意一个 occurrence，`remove_random()` 在所有 occurrence 中均匀选一个并返回其值；若题目要求不同 value 等概率，算法需改。
- Hash/set 操作按平均 O(1) 讨论，随机下标由均匀随机源提供；最坏 hash 冲突不保证常数。
解题路线
- 数组 values 存每个 occurrence；map[value] 存该值的全部数组下标。add 在尾部追加并将新下标放集合。
- 删指定值时从其索引集合取任一位置 i，把数组最后一个值搬到 i，更新被搬值的索引集合：删旧末尾索引，加 i；再弹数组尾并清理空集合。若 i 本就是尾部，不能多做一次重映射。
- remove_random 先按数组长度均匀取下标，再复用同一个 `_remove_at(i)`；数组每个位置对应一次 occurrence，因此 occurrence 等概率。
- 若删除的 value 与末尾 value 相同，索引集合的删除/加入顺序尤其容易写错；验证应比较所有 value 的索引集合与数组实际位置。
手动走一遍
values=[A,B,A]，indices[A]={0,2}。删下标 0 的 A，搬末尾 A 到位置 0，再删尾位置 2；结果 [A,B]，A 的索引集合只剩 {0}。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
from random import randrange
class RandomizedMultiset:
def __init__(self):
self.values = []
self.indices = defaultdict(set)
def add(self, value):
index = len(self.values)
self.values.append(value)
self.indices[value].add(index)
def remove(self, value) -> bool:
if not self.indices.get(value):
return False
index = next(iter(self.indices[value]))
self._remove_at(index)
return True
def _remove_at(self, index):
value = self.values[index]
last_index = len(self.values) - 1
last_value = self.values[last_index]
self.indices[value].remove(index)
if index != last_index:
self.values[index] = last_value
self.indices[last_value].remove(last_index)
self.indices[last_value].add(index)
self.values.pop()
if not self.indices[value]:
del self.indices[value]
return value
def remove_random(self, choose_index=randrange):
if not self.values:
raise IndexError("empty collection")
return self._remove_at(choose_index(len(self.values)))
复杂度
add/remove/remove_random 平均 O(1) 时间，存储 O(N) occurrences；随机删除均匀性依赖 choose_index 均匀。5,000 组随机操作序列与独立 Counter/索引重算 oracle 对照。
易错点与追问
容易失分的边界
- 删除中间项只弹数组，后续索引全部错位。
- 搬末尾后忘了更新其索引集合。
- 末尾值与被删值相同时重复移除同一索引。
- 随机从 distinct key 中选，误变成 value 等概率。
- 声称 hash 表严格最坏 O(1)。
继续深挖
- 如果要按不同 value 均匀随机，结构如何变？
- remove(value) 必须删最早插入 occurrence 时还能 O(1) 吗？
- 并发 add/remove_random 如何锁？
- 支持权重随机时如何扩展？
