很容易想到O(1)时间判断是否存在并插入删除需要用到map，O(1)时间实现随机返回要用到数组。
所以就结合map和数组来实现这个类。
基本思路是用map来保存val到idx的映射，在vector中按idx来保存val。
需要注意的一点是remove一个元素时，不能直接在vector中erase然后改变map[val]的值，这样map[val]后面元素对应的索引不变就会出问题。
举个例子：
insert(100),insert(101),remove(100);
第一步insert(100)的时候让map[100] = 1; vector[1] = 100;(这里让vector的下标从1开始)
第二步insert(101)的时候让map[101] = 2; vector[2] = 101;
第三步remove(100)的时候 (重点来了)
直接在vector中erase(100)会导致101在vector中的索引变成1，而map[101]此时还等于2，这个时候就会出现问题了。仔细思考一下就会发现remove(val)的时候，会让val后面添加的值的索引减1，而map里的索引不能挨个改变，改变的话就不是O(1)了。所以解决办法就是想办法让每个remove的值都是最后一个。
也就是先和最后一个元素交换，再直接pop_back()就行了。
class RandomizedSet {
public:
vector<int> nums;
map<int, int> idx;
int len;
RandomizedSet() {
nums.clear();
nums.push_back(0);
idx.clear();
len = 0;
}
bool insert(int val) {
if(idx[val] == 0){
idx[val] = ++ len;
nums.push_back(val);
return true;
}
return false;
}
bool remove(int val) {
if(idx[val] != 0){
//这里先和最后一个元素交换位置再pop
nums[idx[val]] = nums[len];
idx[nums[idx[val]]] = idx[val];
nums.pop_back();
idx[val] = 0;
len --;
return true;
}
return false;
}
int getRandom() {
return nums[rand() % len + 1];
}
};
/**
* 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();
*/
