题目描述

设计一个支持在 平均 时间复杂度 $O(1)$ 下，执行以下操作的数据结构。

注意：允许出现重复元素。

• insert(val)：向集合中插入元素 val。
• remove(val)：当 val 存在时，从集合中移除一个 val。
• getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈 线性相关。

样例

// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();

// 向集合中插入 1。返回 true 表示集合不包含 1。
collection.insert(1);

// 向集合中插入另一个 1。返回 false 表示集合包含 1。集合现在包含 [1,1]。
collection.insert(1);

// 向集合中插入 2，返回 true。集合现在包含 [1,1,2]。
collection.insert(2);

// getRandom 应当有 2/3 的概率返回 1，1/3 的概率返回 2。
collection.getRandom();

// 从集合中删除 1，返回 true。集合现在包含 [1,2]。
collection.remove(1);

// getRandom 应有相同概率返回 1 和 2。
collection.getRandom();

算法

(哈希表) $O(1)$

1. 定义一个哈希表 hash，和一个数组 nums。其中 nums 数组记录目前所有的数字，hash 记录每个数字在数组中的所有位置（对应一个集合）。
2. 插入操作：在哈希表中对应位置的集合中插入新位置 nums.size()，并在 nums 中插入当前数字。
3. 删除操作：如果 nums 末尾的数字等于待删除数字，则直接删除。否则，取出 val 中的任意一个位置（代码里取了第一个位置），然后和数组末尾元素交换，并更新哈希表。交换后，删除数组末尾的数字。
4. 返回时，直接随机一个下标，然后数组 nums 中这个下标的数字。

时间复杂度

• 由于哈希表操作的时间复杂度为 $O(1)$，所以每个操作的时间复杂度都是 $O(1)$。

C++ 代码

class RandomizedCollection {
public:
    /** Initialize your data structure here. */
    unordered_map<int, unordered_set<int>> hash;
    vector<int> nums;

    RandomizedCollection() {

    }

    /**
     * Inserts a value to the collection.
     * Returns true if the collection did not already contain the specified element.
     */
    bool insert(int val) {
        bool ret = hash.find(val) == hash.end();
        hash[val].insert(nums.size());
        nums.push_back(val);
        return ret;
    }

    /**
     * Removes a value from the collection.
     * Returns true if the collection contained the specified element.
     */
    bool remove(int val) {
        if (hash.find(val) != hash.end()) {
            if (nums.back() == val) {
                nums.pop_back();
                hash[val].erase(nums.size());
                if (hash[val].empty())
                    hash.erase(val);
                return true;
            }

            int t = *hash[val].begin();

            hash[nums.back()].erase(nums.size() - 1);
            hash[nums.back()].insert(t);

            swap(nums[t], nums.back());

            nums.pop_back();
            hash[val].erase(t);
            if (hash[val].empty())
                hash.erase(val);
            return true;
        }

        return false;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */