Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ boolinsert(int val){ auto result = map.find(val) == map.end(); map[val].push_back(vector.size()); vector.push_back({val, map[val].size() - 1});
return result; }
/** Removes a value from the collection. Returns true if the collection contained the specified element. */ boolremove(int val){ auto result = map.find(val) != map.end();
if(result) { auto last = vector.back(); map[last.first][last.second] = map[val].back(); vector[map[val].back()] = last; map[val].pop_back(); if(map[val].empty()) { map.erase(val); } vector.pop_back(); }
return result; }
/** Get a random element from the collection. */ intgetRandom(){ returnvector[rand() % vector.size()].first; } };
/** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection* obj = new RandomizedCollection(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */