Java O(B) constructor and O(1) pick, HashMap
The idea is very simple, we have elements in the blacklist which we should not pick, so we need to remap these elements to some other values.\n\nFor the first l
The idea is very simple, we have elements in the blacklist which we should not pick, so we need to remap these elements to some other values.\n\nFor the first loop, we make a set that records all elements from blacklist that are smaller than N, these elements should not be picked, the set has size count.\nWe then know the uniform random distribution interval, which is \\[0,M) where M = N-count. (In other words, there are M uniform-randomly distributed elements), and we initialize our random key to be in this interval.\n\nFor the second loop, we remap all elements from blacklist that are in range \\[0, M), we just need to remap them to values in  \\[M, N).  But we need to be careful as there may be some elements in \\[M, N) that are also in the blacklist, we just need to skip them.\n```\nclass Solution {\n    private Map<Integer, Integer> map;\n    private int key;\n    private int M;\n    public Solution(int N, int[] b) {\n        Set<Integer> set = new HashSet<>();\n        for(int c : b){\n            if(c < N){\n                set.add(c);\n            }\n        }\n        M = N - set.size();\n        Random r = new Random();\n        key = r.nextInt(M);\n        map = new HashMap<>();\n        int count = 0;\n        for(int c : b){\n            if(c < M){\n                while(set.contains(M + count)){\n                    count++;//skip elements in blacklist\n                }\n                map.put(c, M+count++);\n            }\n        }\n    }    \n    public int pick() {\n        int k = key;\n        key = (k+1) % M;\n        return map.getOrDefault(k, k);\n    }\n}\n```
[]