類似第380題，唯一不同是，可能有重復(fù)元素
要求用O(1)的時(shí)間復(fù)雜度實(shí)現(xiàn)插入、刪除和隨機(jī)輸出一個(gè)值，用python的SortedList就完全不是Hard題了
插入：
用dict判斷該元素是否已經(jīng)存在，如果不存在，則SortedList add這個(gè)元素，dict記錄這個(gè)元素出現(xiàn)過幾次
刪除：
SortedList 刪除元素O(logn)
隨機(jī)輸出list中的一個(gè)值：
python有現(xiàn)成函數(shù)：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()