0380. Insert Delete GetRandom O(1) ================================= 题目信息 -------- :题号: 0380 :难度: Medium :主题: 设计、集合、随机返回、平均常数时间 :原题: `LeetCode 0380 `_ :重点: 集合不允许重复值、插入删除返回是否改变集合、随机返回现有元素且概率相等、三种操作平均 O(1) 题目重述 -------- 实现 ``RandomizedSet`` 类。``insert(val)`` 在 ``val`` 不存在时把它加入集合并返回 ``true``,已存在时不改变集合并返回 ``false``;``remove(val)`` 在 ``val`` 存在时删除它并返回 ``true``,不存在时返回 ``false``;``getRandom()`` 从当前集合中随机返回一个元素。 ``getRandom`` 调用时集合保证非空,并且当前每个元素被返回的概率必须相同。三个操作都要求平均时间复杂度为 ``O(1)``。``val`` 位于 32 位有符号整数范围内,对对象的调用总数不超过 ``2 * 10^5``;同一对象需要在连续调用之间保存集合状态。 自建示例 -------- 插入、重复插入与删除: .. code-block:: text 调用:insert(4), insert(9), insert(4), remove(4), getRandom() 输出:true, true, false, true, 9 解释:第二次插入 4 不改变集合;删除 4 后只剩 9,因此随机调用必须返回 9。 随机结果必须来自现有集合: .. code-block:: text 调用:insert(-2), insert(7), getRandom() 输出:前两次为 true;最后一次可以是 -2 或 7 解释:两个现有元素应具有相同被选概率,不能返回集合之外的值。 数组负责随机,哈希表负责定位 ------------------------------ 用动态数组保存所有元素,用哈希表记录“值到数组下标”的映射。数组可以按下标等概率随机访问,哈希表可以平均常数时间判断存在性;删除时把末尾元素搬到待删位置,再弹出末尾,从而避免移动中间的大段元素,并同步更新搬来元素的下标。 C++ 实现 -------- .. code-block:: cpp class RandomizedSet { std::vector values; std::unordered_map index; std::mt19937 generator{std::random_device{}()}; public: bool insert(int val) { if (index.count(val) != 0) return false; index[val] = static_cast(values.size()); values.push_back(val); return true; } bool remove(int val) { auto it = index.find(val); if (it == index.end()) return false; int removed = it->second; int last = values.back(); values[removed] = last; index[last] = removed; values.pop_back(); index.erase(it); return true; } int getRandom() { std::uniform_int_distribution distribution( 0, static_cast(values.size()) - 1); return values[distribution(generator)]; } }; 代码分析 -------- 删除末尾元素时,即使 ``last == val``,先更新再删除映射也会得到正确的空缺状态;否则则把最后一个值的映射改到被删除的位置。数组中的每个元素位置等概率,因此随机返回满足均匀性要求。三种操作平均时间为 ``O(1)``,额外空间为 ``O(m)``,其中 ``m`` 是当前元素数。