381. Insert Delete GetRandom O(1) - Duplicates allowed
设计数据结构， 这种题目还是挺巧妙的
class RandomizedCollection(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.h = {}
self.arr = []
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
"""
self.arr.append(val)
if val in self.h:
self.h[val].add(len(self.arr) - 1)
return False
else:
self.h[val] = set([len(self.arr) - 1])
return True
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 val in self.h and self.h[val]:
out, ins = self.h[val].pop(), self.arr[-1] # val的一个index，和最后一个值
self.arr[out] = ins # 把那个index的值设置为arr的最后一个值
if self.h[ins]: # 如果arr的最后一个值存在于h里
self.h[ins].add(out)
self.h[ins].discard(len(self.arr) - 1)
self.arr.pop() #删掉arr的最后一个值
return True
return False
def getRandom(self):
"""
Get a random element from the collection.
:rtype: int
"""
return random.choice(self.arr)
# 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()
