类似第380题，唯一不同是，可能有重复元素
要求用O(1)的时间复杂度实现插入、删除和随机输出一个值，用python的SortedList就完全不是Hard题了
插入：
用dict判断该元素是否已经存在，如果不存在，则SortedList add这个元素，dict记录这个元素出现过几次
删除：
SortedList 删除元素O(logn)
随机输出list中的一个值：
python有现成函数：random.choice
1 #381
2 #Runtime: 661 ms
3 #Memory Usage: 70.6 MB
4
5 from sortedcontainers import SortedList
6
7 class RandomizedCollection(object):
8
9 def __init__(self):
10 self.random_set = SortedList([])
11 self.id_dict = defaultdict(lambda:0)
12
13 def insert(self, val):
14 """
15 :type val: int
16 :rtype: bool
17 """
18 self.random_set.add(val)
19 self.id_dict[val] += 1
20 return self.id_dict[val] == 1
21
22 def remove(self, val):
23 """
24 :type val: int
25 :rtype: bool
26 """
27 if self.id_dict[val] == 0:
28 return False
29 self.random_set.remove(val)
30 self.id_dict[val] -= 1
31 return True
32
33 def getRandom(self):
34 """
35 :rtype: int
36 """
37 return random.choice(self.random_set);
38
39
40 # Your RandomizedCollection object will be instantiated and called as such:
41 # obj = RandomizedCollection()
42 # param_1 = obj.insert(val)
43 # param_2 = obj.remove(val)
44 # param_3 = obj.getRandom()