Java Binary Search Solution O(BlogB) for constructor and O(logB) for pick()
Constructor: Sort the blacklist then build the intervals list. e.g. N = 10, blacklist = [3, 8, 7, 6], we will have intervals: [0, 2], [4, 5], [9, 9]. Because of
`Constructor`: Sort the blacklist then build the intervals list. e.g. `N = 10`, `blacklist = [3, 8, 7, 6]`, we will have intervals: `[0, 2], [4, 5], [9, 9]`. Because of the sorting, time complexity is `O(BlogB)`, where `B` is the length of blacklist.\n\n`pick()`: Use one time `random.nextInt(l)` to get the `index` of the number, where `l = N - B`. Then use binary search to search for the interval which contains the `indexth` number. The process will take `O(logB)` time.\n\nSpace complexity: `O(B)` for the interval list.\n\nUse one time `random.nextInt()` for each `pick()`.\n\n```\nclass Solution {\n    \n    class Interval {\n        int low;\n        int high;\n        int preCount;\n        Interval(int low, int high, int preCount) {\n            this.low = low;\n            this.high = high;\n            this.preCount = preCount;\n        }\n    }\n    \n    private List<Interval> intervals;\n    private Random r;\n    private int l;\n\n    public Solution(int N, int[] blacklist) {\n        Arrays.sort(blacklist);\n        intervals = new ArrayList<>();\n        r = new Random();\n        l = N - blacklist.length;\n        int pre = 0, count = 0;\n        for (int b : blacklist) {\n            if (pre != b) {\n                intervals.add(new Interval(pre, b - 1, count));\n                count += b - pre;\n            }\n            pre = b + 1;\n        }\n        intervals.add(new Interval(pre, N - 1, count));\n    }\n    \n    public int pick() {\n        int index = r.nextInt(l);\n        int low = 0, high = intervals.size() - 1;\n        while (low <= high) {\n            int mid = low + (high - low) / 2;\n            Interval cur = intervals.get(mid);\n            if (cur.preCount <= index && index < cur.preCount + cur.high - cur.low + 1) {\n                return cur.low + index - cur.preCount;\n            } else if (cur.preCount > index) {\n                high = mid - 1;\n            } else {\n                low = mid + 1;\n            }\n        }\n        return -1;\n    }\n}\n```
[]