# Python solution a little bit different from 380

• 380 dic tracks one position in list, now dic tracks all the positions in list. Use self.count to track the valid length of list, so there is no need to shrink list.

import random
class RandomizedCollection(object):

def __init__(self):
"""
"""
self.dic = {}
self.nums = []
self.count = 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
"""
flag = False
if val not in self.dic:
self.dic[val] = set()
flag = True
# never shrink list, so count is true size
if self.count == len(self.nums):
self.nums.append(val)
else:
self.nums[self.count] = val
self.count += 1
return flag

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 not in self.dic:
return False
pos = self.dic[val].pop()
if len(self.dic[val]) == 0:
del self.dic[val]
# fill with last num
if pos != self.count - 1:
self.nums[pos] = self.nums[self.count - 1]
self.dic[self.nums[pos]].remove(self.count - 1)
self.count -= 1
return True

def getRandom(self):
"""
Get a random element from the collection.
:rtype: int
"""
return self.nums[random.randint(0, self.count - 1)]

# 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()

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.