Insert|Insert Delete GetRandom O(1) - Duplicates allowed
【Insert|Insert Delete GetRandom O(1) - Duplicates allowed】题目来源
和上一题有点类似，求插入删除取随机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> maps;
vector> 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();
*/
推荐阅读
- 关于mybatis的 insert into select 命令未结束问题
- C++|【C++】new/delete对象过程
- #|C++ new/delete和new[ ]/delete[ ] 深入解析
- SAP|SAP ABAP OData 服务如何支持删除(Delete)操作试读版
- 写一个Delete程序去忘记
- 在python中使用pymysql往mysql数据库中插入(insert)数据实例
- Mysql之LAST_INSERT_ID
- Mybatis注解方式@Insert的用法
- Leetcode PHP题解--D138 35. Search Insert Position
- client-go|client-go gin的简单整合十一-Delete