LeetCode/solutions/380. Insert Delete GetRandom O(1).md

380. Insert Delete GetRandom O(1)

思路

要求设计一个集合类，要在O(1)时间内插入、删除以及随机返回一个元素。 如果不考虑随机返回一个元素的话，那么这个类就是unordered_set，它可以在常数时间复杂度进行插入和删除。

现在要考虑在常数时间返回一个随机元素，即要考虑以常数时间根据索引取值，满足这个特性的只有数组。所以我们以用unordered_map记录元素到数组索引的映射， 这样就可以在常数时间返回一个随机元素。不过为了以常数时间复杂度进行删除操作，需要变通一下：将待删除的元素和数组末元素交换一下，然后删除末尾元素。

rand()产生0到RAND_MAX之间的随机数，在头文件stdlib.h内。

C++

class RandomizedSet {
private:
    vector<int>data;
    unordered_map<int, int>idx_map;

public:
    /** Initialize your data structure here. */
    RandomizedSet() {}
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(idx_map.count(val)) return false;
        idx_map[val] = data.size();
        data.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(!idx_map.count(val)) return false;
        
        int idx = idx_map[val];
        data[idx] = data.back();
        idx_map[data.back()] = idx;
        
        idx_map.erase(val);
        data.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return data[rand() % data.size()];
    }
};