⓺➀ Insert Delete GetRandom O(1)
Top Interview 150, Data Structure, Leetcode medium, Algorithm, C++
Today’s code
Idea
這裡利用了map與vector兩個資料結構共同去解決此問題，map中的兩個鍵值（key, value）分別儲存：
key: key值儲存所輸入的val，我們可以利用val去搜尋是否以經有val的存在且時間複雜度為O(1)。
value: value值所儲存的是val在vector之中的索引（index），用於我們隨機存取。
這裡有一個有趣的規劃是，我們新增新的val值在vector時，都是從後面加入的也就是push_back，如此我們可以透過運算（vector.size() — 1）來確保目前要新增的值的索引值（index）並將其儲存在map所對應的value值中。
當然我們要移除元素時，我們事先透過map.find(val)搜尋，是否已經有val存在了，若有則取出他的value（也就是我們所儲存的val在vector之中的索引值index）
接著，我們將vector的最後一個元素賦值我們所搜尋到的索引的值，也就是說我們的目標移除的元素已經不在了，他變成了原本vector最後一個元素。
好的問題來了，目前vector有兩個元素是相同的，那就是vector的最後一個元素（vector.back()），我們只需要把vector的最後一個元素消除（erase）之後vector之中的每一個元素就會都是獨一無二的了。
更新完vector之後還要再更新map，因為原先map之中vector.back()的value已經改變，變成了我們最一開始要消除的val的索引值（pop.back()）。
所以，map[vector[欲刪除的索引值]] ＝ 欲刪除的索引值。用來更新整理map中vector的最後一個元素的index值（map的value值）。
最後再把map中的val刪掉。
class RandomizedSet {
private:
unordered_map<int, int>test_map;
vector<int> myvector;
public:
RandomizedSet() {
srand(time(NULL));
}
bool insert(int val) {
if(test_map.find(val) == test_map.end()){
myvector.push_back(val);
test_map[val] = myvector.size() - 1;
return true;
}else{
return false;
}
}
bool remove(int val) {
if(test_map.find(val) == test_map.end()){
return false;
}else{
auto tmp_it = test_map.find(val);
myvector[tmp_it->second] = myvector.back();
myvector.pop_back();
test_map[myvector[tmp_it->second]] = tmp_it->second;
test_map.erase(val);
return true;
}
}
int getRandom() {
int index = rand() % myvector.size();
return myvector[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();
*/
