class RandomizedSet {
public:
unordered_map<int, int> Map;
vector<int> arr;
RandomizedSet() {
}
bool insert(int val) {
if (Map.count(val)) return false;
Map[val] = arr.size();
arr.push_back(val);
return true;
}
bool remove(int val) {
if (!Map.count(val)) return false;
arr[Map[val]] = arr.back();
Map[arr.back()] = Map[val];
arr.pop_back();
Map.erase(val);
return true;
}
int getRandom() {
return arr[rand() % arr.size()];
}
};
/**
* 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();
*/Time Complexity: O(1)
Space: O(n)
