-
Notifications
You must be signed in to change notification settings - Fork 62
/
randomized_set.py
40 lines (33 loc) · 1.01 KB
/
randomized_set.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
import random
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.dic = {}
self.lis = []
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.dic:
return False
self.lis.append(val)
self.dic[val] = len(self.lis) - 1
return True
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val not in self.dic:
return False
last, idx = self.lis[-1], self.dic[val]
self.lis[idx], self.dic[last] = last, idx
self.lis = self.lis[:-1]
self.dic.pop(val)
return True
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return random.choice(self.lis)