380. 常數(shù)時間插入暮顺、刪除和獲取隨機元素
設計一個支持在*平均 *時間復雜度 O(1) 下厅篓，執(zhí)行以下操作的數(shù)據(jù)結(jié)構。
insert(val)：當元素 val 不存在時捶码，向集合中插入該項羽氮。remove(val)：元素 val 存在時，從集合中移除該項惫恼。getRandom：隨機返回現(xiàn)有集合中的一項档押。每個元素應該有相同的概率被返回。
思路：
構建兩個map祈纯，第一個map存儲<val令宿，index>，index為val進入map的的順序腕窥，可根據(jù)val查找index粒没；第二個map存儲<index，val>正好和第一個反過來簇爆，可根據(jù)index查找val癞松。還需要維護一個size，表示當前有幾個元素入蛆。
插入：先判斷能否插入响蓉，若能則兩個map均插入，同時size+1哨毁；
獲确慵住：返回第二個map的一個隨機索引；
刪除：先判斷第一個map是否存在待刪除元素挑庶，若存在言秸，則根據(jù)第一個map獲取待刪除val的index，并將該index賦值給第一個map的最后一個元素迎捺，并將該元素賦值給第二個map對應的index举畸，最后將第一個map對應的val條目刪除，將第二個map的最后一個index刪除凳枝，并將size-1抄沮。這種操作保證了index的連續(xù)性跋核，獲取隨機元素時能保證取得到。
c++語言細節(jié)：
兩個map要做為類的數(shù)據(jù)成員叛买，不能聲明在某個函數(shù)中砂代；
map.find(K)，如果map中存在K率挣，則返回指向該元素得迭代器刻伊，若不存在，則返回end()尾后迭代器椒功；
可以通過map[k]=val捶箱，進行賦值；
map.erase(it)动漾，是接收迭代器參數(shù)的丁屎；
c++沒有生成0-1的隨機數(shù)發(fā)生器，可以通過rand()%n旱眯，來獲取0~n-1之間的整數(shù)晨川；
class RandomizedSet {
public:
map<int, int> kindex; // 第一個map k index
map<int, int> indexK; // 第二個map index K
int size; //元素個數(shù)
/** 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();
*/
