380. 常数时间插入、删除和获取随机元素
设计一个支持在*平均 *时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。remove(val)：元素 val 存在时，从集合中移除该项。getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
思路：
构建两个map，第一个map存储<val，index>，index为val进入map的的顺序，可根据val查找index；第二个map存储<index，val>正好和第一个反过来，可根据index查找val。还需要维护一个size，表示当前有几个元素。
插入：先判断能否插入，若能则两个map均插入，同时size+1；
获取：返回第二个map的一个随机索引；
删除：先判断第一个map是否存在待删除元素，若存在，则根据第一个map获取待删除val的index，并将该index赋值给第一个map的最后一个元素，并将该元素赋值给第二个map对应的index，最后将第一个map对应的val条目删除，将第二个map的最后一个index删除，并将size-1。这种操作保证了index的连续性，获取随机元素时能保证取得到。
c++语言细节：
两个map要做为类的数据成员，不能声明在某个函数中；
map.find(K)，如果map中存在K，则返回指向该元素得迭代器，若不存在，则返回end()尾后迭代器；
可以通过map[k]=val，进行赋值；
map.erase(it)，是接收迭代器参数的；
c++没有生成0-1的随机数发生器，可以通过rand()%n，来获取0~n-1之间的整数；
class RandomizedSet {
public:
map<int, int> kindex; // 第一个map k index
map<int, int> indexK; // 第二个map index K
int size; //元素个数
/** Initialize your data structure here. */
RandomizedSet() {
size = 0;
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
auto it = kindex.find(val);
if (it == kindex.end()) //说明该元素不存在，可以插入
{
kindex[val] = size;
indexK[size++] = val;
return true;
}
else
return false;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
auto it = kindex.find(val);
if (it != kindex.end()) //说明map中有该元素，可以删除
{
int index = kindex[val]; //获取该元素对应的index
int lastIndex = --size; // 获取最后一个元素的index
int lastK = indexK[lastIndex]; //获取最后一个元素的值
indexK[index] = lastK; //将待删除元素对应的index的值改忘最后一个元素的值
kindex[lastK] = index; //将最后一个元素的index改为待删除元素的index
indexK.erase(lastIndex);//删除最后一个元素的原索引
kindex.erase(val); //删除待删除元素的值
return true;
}
else
return false;
}
/** Get a random element from the set. */
int getRandom() {
if (size == 0) //没有元素了，返回0
return 0;
int index = rand() % size; //返回0~size-1
return indexK[index];
}
};
/**
* 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();
*/
