Force buckle 710 Random numbers in the blacklist

Title source ：https://leetcode.cn/problems/random-pick-with-blacklist/

General meaning ：
Given a range of numbers n, An array of blacklists , Design a class return 0 To n - 1 Between random numbers that are not in the blacklist , It is required that the probability of each number being returned should be equal

Ideas

Set the blacklist array length to m, Then the number of returned numbers is n - m individual

So you can set the random number bound by n - m

• If the number in the blacklist is greater than or equal to bound, Then you don't have to do anything
• If the number in the blacklist is less than bound, You can use a hash table to map it to [bound, n - 1] in . In this way, the blacklist generated by the random number generator is less than bound The number of hours , Directly map to another number

Code ：

public class Pick {
    
    //  The mapping blacklist is less than  bound  Number of numbers 
    Map<Integer, Integer> map;
    int bound;
    Random random;

    public Pick(int n, int[] blacklist) {
    
        map = new HashMap<>();
        int m = blacklist.length;
        //  initialization  bound
        bound = n - m;
        random = new Random();
        //  Save the hash table of blacklist numbers 
        Set<Integer> blackSet = new HashSet<>();
        for (int num : blacklist) {
    
            if (num >= bound) {
    
                blackSet.add(num);
            }
        }
        //  Mapping index 
        int idx = bound;
        //  Traverse the blacklist 
        for (int num : blacklist) {
    
            //  If the blacklist number is less than  bound, Map it to  [bound, n - 1]  The number that is not in the blacklist and has not been mapped 
            if (num < bound) {
    
                //  If the current number to be mapped is in the blacklist , Indexes  +1
                while (blackSet.contains(idx)) {
    
                    idx++;
                }
                map.put(num, idx++);
            }
        }
    }

    public int pick() {
    
        //  Generate random number 
        int x = random.nextInt(bound);
        //  Return random number , If the random number is  map  in , Returns the number of its mapping 
        return map.getOrDefault(x, x);
    }

}