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;同一对象需要在连续调用之间保存集合状态。

自建示例

插入、重复插入与删除:

调用:insert(4), insert(9), insert(4), remove(4), getRandom()
输出:true, true, false, true, 9
解释:第二次插入 4 不改变集合;删除 4 后只剩 9,因此随机调用必须返回 9。

随机结果必须来自现有集合:

调用:insert(-2), insert(7), getRandom()
输出:前两次为 true;最后一次可以是 -2 或 7
解释:两个现有元素应具有相同被选概率,不能返回集合之外的值。

数组负责随机,哈希表负责定位

用动态数组保存所有元素,用哈希表记录“值到数组下标”的映射。数组可以按下标等概率随机访问,哈希表可以平均常数时间判断存在性;删除时把末尾元素搬到待删位置,再弹出末尾,从而避免移动中间的大段元素,并同步更新搬来元素的下标。

C++ 实现

class RandomizedSet {
    std::vector<int> values;
    std::unordered_map<int, int> index;
    std::mt19937 generator{std::random_device{}()};

public:
    bool insert(int val) {
        if (index.count(val) != 0) return false;
        index[val] = static_cast<int>(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<int> distribution(
            0, static_cast<int>(values.size()) - 1);
        return values[distribution(generator)];
    }
};

代码分析

删除末尾元素时,即使 last == val,先更新再删除映射也会得到正确的空缺状态;否则则把最后一个值的映射改到被删除的位置。数组中的每个元素位置等概率,因此随机返回满足均匀性要求。三种操作平均时间为 O(1),额外空间为 O(m),其中 m 是当前元素数。