Insert Delete GetRandom O(1) - Duplicates allowed
Problem: Insert Delete GetRandom O(1) - Duplicates allowed
Code in Python:
from collections import defaultdict
class RandomizedCollection(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.m = defaultdict(set)
self.l = []
self.i = 0
def insert(self, val):
"""
Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
:type val: int
:rtype: bool
"""
res = False
if not self.m[val]: res = True
self.m[val].add(self.i)
self.l.append(val)
self.i += 1
return res
def remove(self, val):
"""
Removes a value from the collection. Returns true if the collection contained the specified element.
:type val: int
:rtype: bool
"""
if self.m[val]:
index = self.m[val].pop()
last = self.l[-1]
self.m[last].add(index)
self.m[last].discard(self.i-1)
self.l[index], self.l[-1] = self.l[-1], self.l[index]
self.l.pop()
self.i -= 1
return True
return False
def getRandom(self):
"""
Get a random element from the collection.
:rtype: int
"""
return random.choice(self.l)
# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()