[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed 常数时间内插入删除和获得随机数 - 允许重复
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.
Example:
// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom(); // Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1); // getRandom should return 1 and 2 both equally likely.
collection.getRandom();
这题是之前那道 Insert Delete GetRandom O(1) 的拓展，与其不同的是，之前那道题不能有重复数字，而这道题可以有，那么就不能像之前那道题那样建立每个数字和其坐标的映射了，但是我们可以建立数字和其所有出现位置的集合之间的映射，虽然写法略有不同，但是思路和之前那题完全一样，都是将数组最后一个位置的元素和要删除的元素交换位置，然后删掉最后一个位置上的元素。对于 insert 函数，我们将要插入的数字在 nums 中的位置加入 m[val] 数组的末尾，然后在数组 nums 末尾加入 val，我们判断是否有重复只要看 m[val] 数组只有刚加的 val 一个值还是有多个值。remove 函数是这题的难点，我们首先看 HashMap 中有没有 val，没有的话直接返回 false。然后我们取出 nums 的尾元素，把尾元素 HashMap 中的位置数组中的最后一个位置更新为 m[val] 的尾元素，这样我们就可以删掉 m[val] 的尾元素了，如果 m[val] 只有一个元素，那么我们把这个映射直接删除。然后将 nums 数组中的尾元素删除，并把尾元素赋给 val 所在的位置，注意我们在建立 HashMap 的映射的时候需要用堆而不是普通的 vector 数组，因为我们每次 remove 操作后都会移除 nums 数组的尾元素，如果我们用 vector 来保存数字的坐标，而且只移出末尾数字的话，有可能出现前面的坐标大小超过了此时 nums 的大小的情况，就会出错，所以我们用优先队列对所有的相同数字的坐标进行自动排序，每次把最大位置的坐标移出即可，参见代码如下：
解法一：
class RandomizedCollection {
public:
RandomizedCollection() {}
bool insert(int val) {
m[val].push(nums.size());
nums.push_back(val);
return m[val].size() == ;
}
bool remove(int val) {
if (m[val].empty()) return false;
int idx = m[val].top();
m[val].pop();
if (nums.size() - != idx) {
int t = nums.back();
nums[idx] = t;
m[t].pop();
m[t].push(idx);
}
nums.pop_back();
return true;
}
int getRandom() {
return nums[rand() % nums.size()];
}
private:
vector<int> nums;
unordered_map<int, priority_queue<int>> m;
};
有网友指出上面的方法其实不是真正的 O(1) 时间复杂度，因为优先队列的 push 不是常数级的，博主一看果然是这样的，为了严格的遵守 O(1) 的时间复杂度，我们将优先队列换成 unordered_set，其插入删除的操作都是常数量级的，其他部分基本不用变，参见代码如下：
解法二：
class RandomizedCollection {
public:
RandomizedCollection() {}
bool insert(int val) {
m[val].insert(nums.size());
nums.push_back(val);
return m[val].size() == ;
}
bool remove(int val) {
if (m[val].empty()) return false;
int idx = *m[val].begin();
m[val].erase(idx);
if (nums.size() - != idx) {
int t = nums.back();
nums[idx] = t;
m[t].erase(nums.size() - );
m[t].insert(idx);
}
nums.pop_back();
return true;
}
int getRandom() {
return nums[rand() % nums.size()];
}
private:
vector<int> nums;
unordered_map<int, unordered_set<int>> m;
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/381
类似题目：
参考资料：
https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- SQLite文件查看工具DB Browser for SQLite
- JavaScript中正则表达式test()、exec()、match() 方法
- CSS3实现边框锯齿效果
- Android 简易XML解析
- Android -- 使用ViewPager实现画廊效果
- CodeForces 705B Spider Man (水题)
- iOS 混合网页开发 问题
- Nginx Rewrite规则记录
- 去除右键的opendgl
- B+树的插入、删除（附源代码）
- JDBC02 利用JDBC连接数据库【使用数据库连接池】
- 数据库的SQL优化
- 转 Caffe学习系列(5)：其它常用层及参数
- 2015 CALLED THE INTERFACE OF 2014
- 洛谷P3960 列队 NOIp2017 线段树/树状数组/splay
- upc组队赛1 不存在的泳池【GCD】
- 走上模拟道路 HDU4891
- js实现随机的四则运算题目
- LeetCode: Word Break II 解题报告
- oracle SUM函数