LeetCode-381 Insert Delete GetRandom O(1)

题目描述

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

题目大意

设计一个数据结构，实现以下三种操作：

　　1. 插入：如果插入一个已存在的数字则返回false，否则插入该数字返回true；

　　2. 删除：如果删除一个不存在的数字返回false，否则删除该数字返回true；

　　3. 获得随机数：随机获得已插入的数字其中的一个，保证所有数字都有几率获得。

（PS：插入的数字可以重复。）

示例

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

解题思路

方法类似LeetCode-381，将map<int,int>换成unordered_map<int,unordered_set<int>>即可以。

复杂度分析

时间复杂度：O(1)

空间复杂度：O(N)

代码

class RandomizedCollection {
private:
    vector<int> nums;
    unordered_map<int, unordered_set<int> > index;
    
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) {
        nums.emplace_back(val);
        index[val].insert(nums.size() - 1);
        return index[val].size() == 1;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        auto it = index.find(val);
        if(it != index.end()) {
            auto tmp = *it->second.begin();
            it->second.erase(it->second.begin());
            nums[tmp] = nums.back();
            index[nums.back()].insert(tmp);
            index[nums.back()].erase(nums.size() - 1);
            nums.pop_back();
            if(index[val].empty())
                index.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();
 */