710.leetcode题目讲解(Python):黑名单中的随机数(Random Pick with Blacklist)

题目

题目

解题思路

这道题的我的主要思路是,先通过累积概率选出各个白名单区间,然后再在白名单区间内生成随机数。网上也有一些其他更好的解法,比如对黑名单的成员进行映射等等,但思路不是特别直观,有些解法生成随机数的概率也并不均匀。

参考代码