leetcode_insert_delete_getrandom_O_1

难度：Medium

使用一个hashMap来保存数字，第一位表示元素，第二位为1表示有，为0表示没有。
但这样无法满足随机取数O(1)的要求。如果随机取数要求满足O(1)，则应该属用数组，此时hashMap第二位存储数组的位置。
插入元素a时，先将元素放入vector，然后hashMap中记录下<元素，位置>。
删除元素a时，找到a的位置a_pos，交换vector中a和最后一位的位置，然后pop_back()。再将hashMap中最后一位元素的位置更新为a_pos。

class RandomizedSet {
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(m.count(val)>0)
            return false;
        else
        {
            v.push_back(val);
            m[val] = v.size()-1;
            return true;
        }
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(m.count(val) == 0)
        {
            return false;
        }
        else
        {
            int val_pos = m[val];
            if(val_pos == v.size()-1)
            {
                v.pop_back();
                m.erase(val);
                return true;
            }
            else{
                int back_val = v.back();
                int back_val_pos = v.size()-1;
                v[val_pos] = back_val;
                m[back_val] = val_pos;
                v.pop_back();
                m.erase(val);
                return true;
            }
        }
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return v[rand()%v.size()];
    }
    unordered_map<int,int> m;
    vector<int> v;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

78ms，超过70.87%