Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class RandomizedSet {
- public:
- /** Initialize your data structure here. */
- unordered_map <int , int> idx_val;
- unordered_map <int , int> val_idx;
- int w = 0;
- RandomizedSet() {
- }
- /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
- bool insert(int val) {
- if (val_idx.count(val) > 0)
- return false;
- idx_val[w] = val;
- val_idx[val] = w;
- w++;
- return true;
- }
- /** Removes a value from the set. Returns true if the set contained the specified element. */
- bool remove(int val) {
- if (val_idx.count(val) == 0)
- return false;
- w--;
- int idx_del = val_idx[val];
- int val_w = idx_val[w];
- idx_val[idx_del] = val_w;
- val_idx[val_w] = idx_del;
- val_idx.erase(val);
- idx_val.erase(w);
- return true;
- }
- /** Get a random element from the set. */
- int getRandom() {
- return idx_val[rand() % w];
- }
- };
- /**
- * 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();
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement