# 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.

1. `insert(val)`: Inserts an item val to the collection.
2. `remove(val)`: Removes an item val from the collection if present.
3. `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();
``````

``````class RandomizedCollection {
public:
RandomizedCollection() {}
bool insert(int val) {
m[val].push(nums.size());
nums.push_back(val);
return m[val].size() == 1;
}
bool remove(int val) {
if (m[val].empty()) return false;
int idx = m[val].top();
m[val].pop();
if (nums.size() - 1 != 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;
};
``````

``````class RandomizedCollection {
public:
RandomizedCollection() {}
bool insert(int val) {
m[val].insert(nums.size());
nums.push_back(val);
return m[val].size() == 1;
}
bool remove(int val) {
if (m[val].empty()) return false;
int idx = *m[val].begin();
m[val].erase(idx);
if (nums.size() - 1 != idx) {
int t = nums.back();
nums[idx] = t;
m[t].erase(nums.size() - 1);
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

Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/discuss/85635/c-two-solutions

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/discuss/85541/C%2B%2B-128m-Solution-Real-O(1)-Solution

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/discuss/197641/C%2B%2B-30-ms-hashmap-hashset-and-vector

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation