题目来源
和上一题有点类似，求插入删除取随机O(1)完成，区别在于可以重复。所以maps中需要vector来存储，然后nums中需要存一下这个元素在maps中的vector中的哪个位置。题目不难，就是比较绕。
class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
bool res = true;
if (maps.count(val) != 0)
res = false;
nums.push_back(make_pair(val, maps[val].size()));
maps[val].push_back(nums.size()-1);
return res;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
if (maps.count(val) != 0) {
maps[nums.back().first][nums.back().second] = maps[val].back();
nums[maps[val].back()] = nums.back();
nums.pop_back();
maps[val].pop_back();
if (maps[val].size() == 0)
maps.erase(val);
return true;
}
else
return false;
}
/** Get a random element from the collection. */
int getRandom() {
return nums[rand() % nums.size()].first;
}
private:
unordered_map<int, vector<int>> maps;
vector<pair<int, int>> nums;
};
/**
* 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();
*/
