LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。
注意: 允许出现重复元素。
insert(val)：向集合中插入元素 val。 remove(val)：当 val 存在时，从集合中移除一个 val。 getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。 示例:
// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();
// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);
// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);
// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);
// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();
// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.remove(1);
// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目默认答题模板
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) {
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
}
/** Get a random element from the collection. */
int getRandom() {
}
};
/**
* 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();
*/查的官方题解才看懂这种题如何做
用哈希表 完成相应的功能
unordered_map<int, unordered_set<int>> idx; vector<int> nums;
公共数据 idx用哈希表存储下标
nums 用来存储数据
插入数据
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ bool insert(int val) { nums.push_back(val); idx[val].insert(nums.size() - 1); return idx[val].size() == 1; }
直接插入 nums 存储数据
idx 存储下标问题
idx[val].size() == 1 判断 是否存在一个值val
删除数据
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
if (idx.find(val) == idx.end()) {
return false;
}
int i = *(idx[val].begin());
nums[i] = nums.back();
idx[val].erase(i);
idx[nums[i]].erase(nums.size() - 1);
if (i < nums.size() - 1) {
idx[nums[i]].insert(i);
}
if (idx[val].size() == 0) {
idx.erase(val);
}
nums.pop_back();
return true;
}1. 找不到 val (idx.find(val) == idx.end()） 删除失败 return false；
2. 重置 map位置
idx[val].erase(i); idx[nums[i]].erase(nums.size() - 1); if (i < nums.size() - 1) { idx[nums[i]].insert(i); }
class RandomizedCollection {
public:
unordered_map<int, unordered_set<int>> idx;
vector<int> nums;
/** 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) {
nums.push_back(val);
idx[val].insert(nums.size() - 1);
return idx[val].size() == 1;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
if (idx.find(val) == idx.end()) {
return false;
}
int i = *(idx[val].begin());
nums[i] = nums.back();
idx[val].erase(i);
idx[nums[i]].erase(nums.size() - 1);
if (i < nums.size() - 1) {
idx[nums[i]].insert(i);
}
if (idx[val].size() == 0) {
idx.erase(val);
}
nums.pop_back();
return true;
}
/** Get a random element from the collection. */
int getRandom() {
return nums[rand() % nums.size()];
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed/solution/o1-shi-jian-cha-ru-shan-chu-he-huo-qu-sui-ji-yua-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。