【leetcode】381. O(1) 时间插入、删除和获取随机元素 - 允许重复（insert-delete-getrandom-o1-duplicates-allowed）（模拟）[困难]

链接

https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

耗时

解题：2 h 19 min
题解：9 min

题意

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

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

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

思路

哈希表存每个元素的索引，再用一个 vector 存元素，维护一个 length 表示 vector 中实际还存在元素的长度。删除的时候，将准备删除的元素和最后一个元素换位置，并更新哈希表的索引。

时间复杂度： O ( 1 ) O(1) O(1)

AC代码

class RandomizedCollection {
private:
    int length = 0;
    vector<int> data;
    unordered_map<int, unordered_set<int>> unmpse;
public:
    /** Initialize your data structure here. */
    RandomizedCollection() {

    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        bool is_exist_val = unmpse.find(val) != unmpse.end() && unmpse[val].size() > 0;
        if(length < data.size()) {
           data[length] = val; 
        }
        else {
            data.push_back(val);
        }
        unmpse[val].insert(length);
        length++;
        return !is_exist_val;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        bool is_exist_val = unmpse.find(val) != unmpse.end() && unmpse[val].size() > 0;
        if(is_exist_val) {
            if(data[length-1] != val) {
                unmpse[data[length-1]].erase(unmpse[data[length-1]].find(length-1));
                unmpse[data[length-1]].insert((*(unmpse[val].begin())));
                swap(data[*(unmpse[val].begin())], data[length-1]);
                unmpse[val].erase(unmpse[val].begin());
            }
            else {
                unmpse[val].erase(unmpse[val].find(length-1));
            }
            length--;
            return true;
        }
        return false;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return data[rand() % length];
    }
};

/**
 * 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();
 */