python | solution faster than 97.79% using hashmap with detailed explanation
Imagine we had a list generated by list(range(n-1)), and consider numbers in blacklist as "black numbers" and the rest as "white numbers". We are required to ra
Imagine we had a list generated by `list(range(n-1))`, and consider numbers in blacklist as "black numbers" and the rest as "white numbers". We are required to randomly pick white numbers with equal probability and minimum built-in random operation.\nThe idea is to partition the list into 2 parts: interval [0,`n-len(blacklist)` )  is "white part" and the rest [`n-len(blacklist)`,  n-1] is "black part". We swap the black numbers in white part with white numbers in black part one by one, and mark those white numbers coming from black part in a hashmap in the form of `black number being swapped : white number`, because the black number swapped with the white number is exactly the index of the white number in white part. In this way, after iterating through the blacklist and having all the numbers adjusted,  in `pick()` we can simply randomize a number from 0 to `n-len(blacklist)` as an index and return the white number at that index.\nI hope words like "white number", "black number", "white part", "black part" in my explanation might not sound too confusing to you, since it is the most straightforward way I find so far to see into this question :)\n```\nclass Solution:\n\n    def __init__(self, n: int, blacklist: List[int]):\n        self.hashmap={}\n        for b in blacklist:\n            self.hashmap[b]=-1\n        self.length=n-len(blacklist)\n        flag=n-1\n        for b in blacklist:\n            if b<self.length: \n                while flag in self.hashmap:\n                    flag-=1\n                self.hashmap[b]=flag\n                flag-=1\n            \n    def pick(self) -> int:\n        seed=random.randrange(self.length)\n        return self.hashmap.get(seed,seed)
['Python']