1
# Runtime: 841 ms (Top 10.38%) | Memory: 24.8 MB (Top 56.73%)
2
class Solution:
3

4
    def __init__(self, n: int, blacklist: List[int]):
5
        self.hashmap = {}
6
        for b in blacklist:
7
            self.hashmap[b] = -1
8
        self.length = n - len(blacklist)
9
        flag = n - 1
10
        for b in blacklist:
11
            if b < self.length:
12
                while flag in self.hashmap:
13
                    flag -= 1
14
                self.hashmap[b] = flag
15
                flag -= 1
16

17
    def pick(self) -> int:
18
        seed = random.randrange(self.length)
19
        return self.hashmap.get(seed, seed)
20

21

22
# Your Solution object will be instantiated and called as such:
23
# obj = Solution(n, blacklist)
24
# param_1 = obj.pick()