動機

random題都很奇妙

Problem

You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely returned.

Optimize your algorithm such that it minimizes the call to the built-in random function of your language.

Implement the Solution class:

  • Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.
  • int pick() Returns a random integer in the range [0, n - 1] and not in blacklist. All the possible integers should be equally likely returned.

 

Example 1:

Input["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"][[7, [2, 3, 5]], [], [], [], [], [], [], []]Output[Algorithm, Leetcode, 6, 4, 1, 6, 1, 6, 4]ExplanationSolution solution = new Solution(7, [2, 3, 5]);solution.pick(); // return 6, any integer from [1,4,6] should be ok. Note that for every call of pick, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/3).solution.pick(); // return 4solution.pick(); // return 1solution.pick(); // return 6solution.pick(); // return 1solution.pick(); // return 6solution.pick(); // return 4

 

Constraints:

  • 1 <= n <= 109
  • 0 <= blacklist.length <- min(105, n - 1)
  • 0 <= blacklist[i] < n
  • All the values of blacklist are unique.
  • At most 2 * 104 calls will be made to pick.

Sol

把range減blacklist，再把在這個範圍的blacklist對應到範圍外的數字

class Solution:

    def __init__(self, n: int, bl: List[int]):
        n2n = {}
        bl = set(bl)
        m = n-len(bl)
        replace = n-1
        for b in bl:
            if b < m:
                while replace > m and replace in bl:
                    replace -= 1
                n2n[b] = replace
                replace -= 1
        self.n2n = n2n
        self.m = m
                    

    def pick(self) -> int:
        i = randrange(self.m)
        if i in self.n2n:
            return self.n2n[i]
        else:
            return i