/
381.py
56 lines (45 loc) · 1.7 KB
/
381.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import defaultdict
import random
class RandomizedCollection(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.valList = list()
self.valToIndices = defaultdict(set)
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
"""
ret = ( val in self.valToIndices )
self.valToIndices[ val ].add( len(self.valList) )
self.valList.append( val )
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.valToIndices:
return False
if self.valList[-1] == val: # easy case, last one is val, so we simply remove last one
self.valList.pop()
self.valToIndices[val].remove( len(self.valList) )
else:
# difficult case, last one is not val, so we need to find a index of val, and make that index have lastVal
lastVal = self.valList.pop()
self.valToIndices[ lastVal ].remove( len(self.valList) )
swapIdx = self.valToIndices[ val ].pop()
self.valList[ swapIdx ] = lastVal
self.valToIndices[ lastVal ].add( swapIdx )
if not self.valToIndices[val]:
del self.valToIndices[ val ]
return True
def getRandom(self):
"""
Get a random element from the collection.
:rtype: int
"""
return random.choice( self.valList )