Table of Content
题目
解题思路
这道题的我的主要思路是，先通过累积概率选出各个白名单区间，然后再在白名单区间内生成随机数。网上也有一些其他更好的解法，比如对黑名单的成员进行映射等等，但思路不是特别直观，有些解法生成随机数的概率也并不均匀。
参考代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import random import bisect class Solution: def __init__(self, N, blacklist): self.N = N - 1 self.black = sorted(blacklist) self.range = [] self.weight = [] self.blacklen = len(self.black) if self.blacklen: s = 0 for r in self.black: if r - s >= 1: self.range.append([s, r - 1]) s = r + 1 if s < self.N + 1: self.range.append([s, self.N]) weight = 0 for r in self.range: weight = weight + r[1] - r[0] + 1 self.weight.append(weight) def pick(self) -> int: if self.blacklen: r = self.range[bisect.bisect_left( self.weight, random.randint(1, self.weight[-1]))] return random.randint(r[0], r[1]) if r[1] > r[0] else r[0] else: return random.randint(0, self.N) |
