Python O(BlogB) construction and O(logB*logB) pick
Read some good solutions to achieve O(1) time pick with pre-processing. Here is another choice of trade-off. If the banned numbers are 1 and 4 in 0123456, the m
Read some good solutions to achieve O(1) time pick with pre-processing. Here is another choice of trade-off. If the banned numbers are `1` and `4` in `0123456`, the mapping would be \n```\n  B=[1,4]\n  \n012345\n0_12_3\n```\nso if we generate a random index 3, which should be mapped to 5, the third number that is not in B.\n\nLet `p(i)` denote the number of banned numbers in `B`. We have `5 - p(5) == 3` in this case.\nNote that `i - p(i)` is a monotonic array, we can binary search for the smallest `i` such that `i - p(i) == 3`.\nNote that ` 3<= i <= 3 + len(B)`, and it takes `O(log B)` time to compute each `p(i)`, so the time complexity is `O(log B * log B)` because we call `p(i)` for at most `O(log B)` times.\n```\nclass Solution:\n\n    def __init__(self, N, blacklist):\n        self.b = sorted(list(set(blacklist)))\n        self.N = N\n\n    def pick(self):\n        l = x = random.randint(0, self.N-len(self.b)-1)\n        h = x + len(self.b)\n        while l < h:\n            m = (l + h) // 2\n            if m - bisect.bisect_right(self.b, m) < x: \n                l = m + 1\n            else:\n                h = m\n        return l\n```
[]