Java O(B) / O(1), HashMap
Suppose N=10, blacklist=[3, 5, 8, 9], re-map 3 and 5 to 7 and 6.\n\n\n\nclass Solution {\n    \n    // N: [0, N)\n    // B: blacklist\n    // B1: < N\n    // B2
Suppose N=10, blacklist=[3, 5, 8, 9], re-map 3 and 5 to 7 and 6.\n![image](https://s3-lc-upload.s3.amazonaws.com/users/cafebaby/image_1530657902.png)\n\n```\nclass Solution {\n    \n    // N: [0, N)\n    // B: blacklist\n    // B1: < N\n    // B2: >= N\n    // M: N - B1\n    int M;\n    Random r;\n    Map<Integer, Integer> map;\n\n    public Solution(int N, int[] blacklist) {\n        map = new HashMap();\n        for (int b : blacklist) // O(B)\n            map.put(b, -1);\n        M = N - map.size();\n        \n        for (int b : blacklist) { // O(B)\n            if (b < M) { // re-mapping\n                while (map.containsKey(N - 1))\n                    N--;\n                map.put(b, N - 1);\n                N--;\n            }\n        }\n        \n        r = new Random();\n    }\n    \n    public int pick() {\n        int p = r.nextInt(M);\n        if (map.containsKey(p))\n            return map.get(p);\n        return p;\n    }\n}\n```\n
[]