leet_code_solutions/380_medium_[sense]_insert_delete_getRandom_o(1).py at master · voidsatisfaction/leet_code_solutions · GitHub

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
import random

class RandomizedSet:
    def __init__(self):
        self._value_set = {}
        self._value_list = []


    def insert(self, val: int) -> bool:
        if val in self._value_set:
            return False

        self._value_list.append(val)
        self._value_set[val] = len(self._value_list)-1

        return True


    def remove(self, val: int) -> bool:
        if val not in self._value_set:
            return False

        if len(self._value_list) == 1:
            self._value_list.pop()
        else:
            last_val, val_index = self._value_list[-1], self._value_set[val]
            self._value_list[val_index], self._value_set[last_val] = last_val, val_index
            self._value_list.pop()

        del self._value_set[val]

        return True


    def getRandom(self) -> int:
        return random.choice(self._value_list)


if __name__ == '__main__':
    rs = RandomizedSet()

    rs.insert(0)
    rs.insert(1)
    rs.remove(0)
    rs.insert(2)
    rs.remove(1)

    print(rs._value_set, rs._value_list)

    rs.remove(2)

    print(rs._value_set, rs._value_list)