A random number in the LeetCode 710 blacklist

Given an integer n and a non-duplicated blacklist array of integer blacklists. Design an algorithm to select an integer that is not on the blacklist from any integer in the range of [0, n - 1]. Any integer that is within the above range and is not in the blacklist blacklist should have an equal probability of being returned.

Optimize your algorithm so that it minimizes the number of times the language is called to its built-in random functions.

Implement the solution class:

solution(int n, int blacklist) initializes the integer n and the integer that is blacklisted on the blacklist.

int pick() returns a random integer in the range [0, n - 1] that is not in the blacklist blacklist.

Example 1: Input.

solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]

Output. null, 0, 4, 1, 6, 1, 0, 4]

Interpretation. solution solution = new solution(7, [2, 3, 5]);

solution.pick();Returns 0, any integer of [0,1,4,6] will do. Note that for each pick call, the probability of returning a return of 6 must be equal (i.e. the probability is 1 4).

solution.pick();Return 4

solution.pick();Return 1

solution.pick();Return 6

solution.pick();Return 1

solution.pick();Returns 0

solution.pick();Return 4

Hint:

1 <= n <= 109

0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] All values in blacklist are different. 
pick can be called up to 2 * 104 times

This means that the number of numbers we can select is n - m, where m is the length of the blacklist. We need to select a random number in this n-m, and each number is selected for a record that is 1 (n-m).

We can randomly take a number [0, n-m-1].

If this number is not in the blacklist, you can return it directly. It is not difficult to conclude that the probability at this time is 1 (n-m), which is in line with the title if this number is on the blacklist. We can't return it, then we can convert it into a whitelist number. Since there are m blacklists, if there are x blacklists in the [0,n-m-1] range, then the blacklist in the [n-m+1,n-1] range is m - x, and the whitelist in the [n-m+1,n-1] range is x. Then the probability of selecting the number of blacklists is x (n-m), and the probability of the whitelist in the range of [n-m+1,n-1] is 1 x. Multiplying the two is the probability that the number in the whitelist mapped to will be selected, i.e., 1 (n-m) in summary, and we can use the hash table b2w to maintain this mapping. where key is the number in the blacklist in [0,n-m-1], and value is the number in a randomly found [n-m, n-1] whitelist.

See the specific implementation**.

Mapping numbers from the blacklist to the whitelist language support: python3python3 code:

class solution: def __init__(self, n: int, blacklist: list[int]):m = len(blacklist) self.bound = w = n - m black = self.b2w = {}for b in blacklist: if b < self.bound: while w in black: w += 1 self.b2w[b] = w w += 1 def pick(self) -int: x = randrange(self.bound) return self.b2w.get(x, x)

Let n be the blacklist length.

Time complexity: $o(n)$Space complexity: $o(n)$