O(1) 时间插入、删除和获取随机元素

难度: Hard

RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。

实现 RandomizedCollection 类:

RandomizedCollection()初始化空的 RandomizedCollection 对象。
bool insert(int val) 将一个 val 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 true ，否则返回 false 。
bool remove(int val) 如果存在，从集合中移除一个 val 项。如果该项存在，则返回 true ，否则返回 false 。注意，如果 val 在集合中出现多次，我们只删除其中一个。
int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。

您必须实现类的函数，使每个函数的平均时间复杂度为 O(1) 。

注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。

示例 1:

输入
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
输出
[null, true, false, true, 2, true, 1]

解释
RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
collection.insert(1);   // 返回 true，因为集合不包含 1。
                        // 将 1 插入到集合中。
collection.insert(1);   // 返回 false，因为集合包含 1。
                        // 将另一个 1 插入到集合中。集合现在包含 [1,1]。
collection.insert(2);   // 返回 true，因为集合不包含 2。
                        // 将 2 插入到集合中。集合现在包含 [1,1,2]。
collection.getRandom(); // getRandom 应当:
                        // 有 2/3 的概率返回 1,
                        // 1/3 的概率返回 2。
collection.remove(1);   // 返回 true，因为集合包含 1。
                        // 从集合中移除 1。集合现在包含 [1,2]。
collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。

提示:

-2³¹ <= val <= 2³¹ - 1
insert, remove 和 getRandom 最多总共被调用 2 * 10⁵ 次
当调用 getRandom 时，数据结构中 至少有一个 元素

Submission

运行时间: 297 ms

内存: 69.7 MB

class RandomizedCollection:

    def __init__(self):
        # 存储每个值的下标位置
        self.pos = defaultdict(set)
        self.value = []

    def insert(self, val: int) -> bool:
        self.pos[val].add(len(self.value))
        self.value.append(val)
        return len(self.pos[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.pos[val]:
            return False
        i = self.pos[val].pop()
        if i == len(self.value) - 1:
            self.value.pop()
        else:
            last = self.value.pop()
            self.value[i] = last
            self.pos[last].remove(len(self.value))
            self.pos[last].add(i)
        return True

    def getRandom(self) -> int:
        return choice(self.value)



# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

Explain

该题解使用哈希表 pos 和动态数组 value 来实现 O(1) 时间复杂度的插入、删除和获取随机元素操作。其中，哈希表 pos 用于存储每个元素在 value 中出现的下标位置集合，动态数组 value 用于存储实际的元素值。在插入时，将元素追加到 value 的末尾，并在 pos 中记录该元素的下标；在删除时，将要删除的元素与 value 的最后一个元素交换位置，然后删除最后一个元素，并更新 pos 中的下标信息；在获取随机元素时，直接从 value 中随机选择一个元素返回即可。

时间复杂度: O(1)

空间复杂度: O(n)

class RandomizedCollection:

    def __init__(self):
        # 存储每个值的下标位置
        self.pos = defaultdict(set)
        self.value = []

    def insert(self, val: int) -> bool:
        # 将元素的下标添加到 pos 中
        self.pos[val].add(len(self.value))
        # 将元素追加到 value 的末尾
        self.value.append(val)
        # 如果 pos 中该元素的下标集合长度为 1，说明是新插入的元素，返回 True
        return len(self.pos[val]) == 1

    def remove(self, val: int) -> bool:
        # 如果 pos 中不存在该元素的下标，说明该元素不存在，返回 False
        if not self.pos[val]:
            return False
        # 取出要删除元素的一个下标
        i = self.pos[val].pop()
        # 如果要删除的元素是 value 的最后一个元素，直接删除即可
        if i == len(self.value) - 1:
            self.value.pop()
        else:
            # 将最后一个元素的值赋给要删除元素的下标位置
            last = self.value.pop()
            self.value[i] = last
            # 更新最后一个元素在 pos 中的下标信息
            self.pos[last].remove(len(self.value))
            self.pos[last].add(i)
        return True

    def getRandom(self) -> int:
        # 从 value 中随机选择一个元素返回
        return choice(self.value)

Explore

在`RandomizedCollection`的`remove`方法中，我们通过从`pos[val]`集合中弹出一个元素的下标实现删除一个实例。这个集合中存储了所有`val`值的下标，因此在调用`pop`方法时，它会随机移除并返回一个下标，这样保证了即使`val`值在数组`value`中重复多次，也只删除一个实例。删除操作完成后，会更新其他数据结构以保持一致性。

如果要删除的元素已经是数组`value`的最后一个元素，则无需进行交换。在这种情况下，直接从数组中弹出最后一个元素，并从`pos`的集合中移除相应的下标即可。这简化了操作，并避免了不必要的元素赋值，从而在所有情况下保持了方法的有效性。

确实存在数据不同步的风险，尤其是在遇到异常或操作失败时。为了防止数据不同步，需要确保在删除和插入操作中的每一步都能成功执行。在Python中，`pop`操作通常是安全的，但如果在更新集合`pos`时发生异常，如内存不足导致操作失败，就必须设计错误处理逻辑，例如使用事务性的操作或捕获异常来回滚到操作前的状态，以保持数据的一致性。

这是因为在`RandomizedCollection`中，每个元素（包括重复的值）都以实际出现的次数存储在数组`value`中。因此，当从这个数组中随机选择一个元素时，每个位置被选中的概率确实是相等的，这导致每个元素被返回的概率与其在数组中的实际出现次数成正比。这种设计确保了随机选择的公平性，每个元素的选择概率与其频率成线性关系。