LeetCode/solutions/381. Insert Delete GetRandom O(1) - Duplicates allowed.md

381. Insert Delete GetRandom O(1) - Duplicates allowed

思路

此题是380. Insert Delete GetRandom O(1)的升级版，可参见380题解。

此题与380不同的是380不能有重复数字，而这道题可以有，那么就不能像380那样建立每个数字和其坐标的映射了，因为同一个可能有多个坐标。 虽然不能索引到坐标，但我们可以索引到存放坐标的容器呀，用什么容器呢，一开始我想到vector, 但是在实现后面删除操作的时候没法O(1)，所以只好用unordered_set。

其他的就和380思路大致差不多了，比如为了O(1)删除，需要变通一下：将待删除的元素和数组末元素交换一下，然后删除末尾元素。

C++

class RandomizedCollection {
private:
    vector<int>data;
    unordered_map<int, unordered_set<int>>idx_map;
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) {
        // if(!idx_map.count(val))
        //    idx_map[val] = unordered_set<int>();
     
        idx_map[val].insert(data.size());   
        data.push_back(val);
        return idx_map[val].size() == 1;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if(!idx_map.count(val) || idx_map[val].empty()) return false;
        
        int idx = *idx_map[val].begin();
        
        if(data[idx] != data.back()){ // 一定要加这个条件
            data[idx] = data.back();
            idx_map[data.back()].insert(idx);
            idx_map[data.back()].erase(data.size() - 1);
        }
        
        idx_map[val].erase(idx);
        data.pop_back();
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return data[rand() % data.size()];
    }
};