Leetcode daily question - 710 Random numbers in the blacklist

subject

Given an integer n And a No repetition Blacklist integer array blacklist . Design an algorithm , from [0, n - 1] Select one of any integers in the range Not joined The blacklist blacklist The integer of . Any within the above scope and not on the blacklist blacklist All integers in should have Equal possibility Returned .

Optimize your algorithm , Minimize the call language built-in The number of random functions .

Realization Solution class :

• Solution(int n, int[] blacklist) Initialize integer n And being blacklisted blacklist The integer of
• int pick() Returns a range of [0, n - 1] And not on the blacklist blacklist Random integers in

Example

Example 1：

Input [“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”,
“pick”] [[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output [null, 0, 4,1, 6, 1, 0, 4]
explain Solution solution = new Solution(7, [2, 3, 5]); solution.pick(); // return 0, whatever [0,1,4,6] All integers are OK . Be careful , For each of these pick Call to ,// 0、1、4 and 6 The return probability of must be equal ( That is, the probability is 1/4).
solution.pick(); // return 4 solution.pick(); // return 1
solution.pick(); // return 6 solution.pick(); // return 1 solution.pick(); // return 0 solution.pick(); // return 4

Tips :

1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] < n
blacklist All values in are Different
pick At most called 2 * 104 Time

Ideas

The idea of commenting on the district boss

Ideas ：

• Blacklist length is s, We from [0, N-s) Take a random value from , This random value may be in the blacklist , What do I do ？
• [0, N-s) Internal elements , If there is i In the blacklist , So in [N-s, N) in , There must be i Elements are not in the blacklist
• Yes [0, N-s) Blacklist elements and [N-s, N) Mapping elements that are not in the blacklist m, It must be one-to-one , It doesn't matter how they correspond
• from [0, N-s) Take a random value from r, If r Not on the blacklist , Go straight back to ; If r In the blacklist , be m[r] It must not be on the blacklist , return m[r]

Answer key

from random import randint

class Solution:

    def __init__(self, N, blacklist):
        """ :type N: int :type blacklist: List[int] """
        self.s = N - len(blacklist)
        #  Less than s A collection of blacklist elements 
        b_lt_s = {i for i in blacklist if i < self.s}
        #  Greater than s A collection of non blacklist elements 
        #  Equivalent to ：w_gt_s = {i for i in range(self.s, N)} - set(blacklist), Thank you for your comments 
        w_gt_s = {
   *range(self.s, N)} - set(blacklist)
        #  Mapping , Use zip Make it convenient 
        #  Equivalent to ：self.m = {k: v for k,v in zip(b_lt_s, w_gt_s)}
        self.m = dict(zip(b_lt_s, w_gt_s))

    def pick(self):
        """ :rtype: int """
        r = randint(0, self.s-1)
        return r if r not in self.m else self.m[r]