380 Insert Delete GetRandom O(1)

class RandomizedSet {
public:
    unordered_map<int, int> vals;
    vector<int> val_array;
    /** 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 ( vals.find(val) != vals.end() ) return false;
        val_array.push_back(val);
        vals.insert(pair<int, int>(val, int(val_array.size()-1)));
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if ( vals.find(val) == vals.end() ) return false;
        int i = vals[val], n = val_array.size();
        vals.erase(vals.find(val));
        if ( i != n-1 ){
            val_array[i] = val_array[n-1];
            vals[val_array[i]] = i;
        }
        val_array.erase(val_array.begin() + n-1);
        return true;
    }

    /** Get a random element from the set. */
    int getRandom() {
        int n = val_array.size();
        if ( n == 0 ) return -1;
        int i = random()%n;
        return val_array[i];
    }
};

/**
 * 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();
 */

Notes
删除的时候，可以只在hashSet里删除。在getRandom()里一直产生随机数直至找到一个仍然在hashSet里的数。但当hashSet的大小远小于数组大小的时候，getRandom()就是O(N)时间了。
更neat的办法，保证hashSet和数组大小一致：当删除val的时候，我们在数组里把val和数组最后一个数交换，然后删去数组最后一个元素即可。这样在getRandom()的时候就是真正的O(1)时间了。