380. O(1) 时间插入、删除和获取随机元素

380. O(1) 时间插入、删除和获取随机元素

每个操作都是
一个保存数的vector，一个从val到vector中idx的映射 map。
vector是为了保证数的idx是连贯的1~n，不会因为remove()操作中间的一个数导致某些idx是空的，无法实现的getRandom()操作。

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
    }
    unordered_map<int,int>mp;
    vector<int>vec;
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(mp.count(val))return false;
        int n=vec.size();
        mp[val]=n;
        vec.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(!mp.count(val))return false;
        int idx=mp[val];
        int lastval=vec.back();
        int idx2=mp[lastval];
        mp[lastval]=idx;
        mp.erase(val);

        swap(vec[idx],vec[idx2]);
        vec.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        int n=vec.size();
        return vec[rand()%n];
    }
};