0381. Insert Delete GetRandom O(1) - Duplicates allowed
=======================================================
题目信息
--------
:题号: 0381
:难度: Hard
:主题: 设计、多重集合、随机实例、平均常数时间
:原题: `LeetCode 0381 `_
:重点: 允许重复插入、删除时只移除一个实例、插入返回此前是否不存在、随机结果按实例等概率
题目重述
--------
实现 ``RandomizedCollection`` 类,它保存一个允许重复值的多重集合。``insert(val)`` 总会加入一个 ``val`` 实例,并在该值插入前不存在时返回 ``true``,此前已经存在一个或多个实例时返回 ``false``。``remove(val)`` 若存在该值,则删除其中任意一个实例并返回 ``true``;不存在时返回 ``false``。
``getRandom()`` 调用时集合保证非空,并从当前所有元素实例中等概率选择一个。因此某个值出现次数越多,它被返回的总概率越高。三种操作都要求平均时间复杂度为 ``O(1)``。``val`` 位于 32 位有符号整数范围内,对对象的调用总数不超过 ``2 * 10^5``,对象状态在连续调用之间保留。
自建示例
--------
重复插入影响返回值和随机概率:
.. code-block:: text
调用:insert(5), insert(5), insert(8), getRandom()
输出:true, false, true;随机结果为 5 或 8
解释:集合包含两个 5 和一个 8,所以 5 被返回的概率为 2/3,8 的概率为 1/3。
一次删除只移除一个实例:
.. code-block:: text
调用:remove(5), getRandom()
输出:true;随机结果为 5 或 8,二者概率相同
解释:删除后仍保留一个 5,集合现在含两个实例。
数组保存实例,值映射到所有实例位置
------------------------------------
允许重复值时,数组中的每个位置代表一个独立实例;哈希表把值映射到这些位置的集合。插入时把新位置加入集合,返回此前该集合是否为空;删除时取出任意一个位置。为了保持数组紧凑,仍把末尾实例搬到被删位置,同时从末尾位置集合中移除旧下标、加入新下标。
随机选择直接在实例数组上取下标,所以出现两次的值天然有两份等概率实例。
C++ 实现
--------
.. code-block:: cpp
class RandomizedCollection {
std::vector values;
std::unordered_map> positions;
std::mt19937 generator{std::random_device{}()};
public:
bool insert(int val) {
bool wasAbsent = positions[val].empty();
positions[val].insert(static_cast(values.size()));
values.push_back(val);
return wasAbsent;
}
bool remove(int val) {
auto it = positions.find(val);
if (it == positions.end() || it->second.empty()) {
return false;
}
int removedIndex = *it->second.begin();
int lastIndex = static_cast(values.size()) - 1;
int lastValue = values[lastIndex];
it->second.erase(removedIndex);
bool removeValueEntry = it->second.empty();
if (removedIndex != lastIndex) {
values[removedIndex] = lastValue;
auto& movedPositions = positions[lastValue];
movedPositions.erase(lastIndex);
movedPositions.insert(removedIndex);
}
values.pop_back();
if (removeValueEntry) positions.erase(val);
return true;
}
int getRandom() {
std::uniform_int_distribution distribution(
0, static_cast(values.size()) - 1);
return values[distribution(generator)];
}
};
代码分析
--------
位置集合与数组始终同步:移动末尾实例后,它在哈希表中的旧位置被替换为新位置,删除一个值的最后实例时才移除该值的映射。数组位置等概率抽样,重复实例会按出现次数累加概率。插入、删除和随机选择平均为 ``O(1)``,额外空间为 ``O(m)``。