题目
题目
解题思路
这道题的我的主要思路是，先通过累积概率选出各个白名单区间，然后再在白名单区间内生成随机数。网上也有一些其他更好的解法，比如对黑名单的成员进行映射等等，但思路不是特别直观，有些解法生成随机数的概率也并不均匀。
参考代码
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)
源码地址：
https://github.com/jediL/LeetCodeByPython
其它题目：[leetcode题目答案讲解汇总（Python版 持续更新）]
(https://www.jianshu.com/p/60b5241ca28e)
ps：如果您有好的建议，欢迎交流 :-D，
也欢迎访问我的个人博客 苔原带 (www.tundrazone.com)
