710. random numbers in the blacklist

Looked at the leetcode My daily question , Topic link ：710. Random numbers in the blacklist
The title is as follows ：

Given an integer n And a No repetition Blacklist integer array blacklist . Design an algorithm , from [0, n - 1] Select one of any integers in the range Not joined The blacklist blacklist The integer of . Any within the above scope and not on the blacklist blacklist All integers in should have Equal possibility Returned .

Optimize your algorithm , Minimize the call language built-in The number of random functions .

Realization Solution class :

Solution(int n, int[] blacklist) Initialize integer n And being blacklisted blacklist The integer of int
pick() Returns a range of [0, n - 1] And not on the blacklist blacklist Random integers in

Tips :

1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <=blacklist[i] < n
blacklist All values in are Different
pick At most called 2 * 104 Time

The first thought to see this problem is Put the data not in the blacklist into a new data , Take another number at random , But the submission found space , Memory limit exceeded , The code is as follows ：

class Solution {
    

    private int n;
    private int[] blacklist;
    private Set<Integer> set;
    private int[] arr;
    private int len;
    private Random random = new Random();

    public Solution(int n, int[] blacklist) {
    

        this.n = n;
        this.blacklist = blacklist;
        this.set = new HashSet();
        this.len = blacklist.length;
        this.arr = new int[n-len];
        for(int i =0;i < blacklist.length;i++){
    
            set.add(blacklist[i]);
        }
        int index = 0;
        for(int i = 0;index < arr.length;i++){
    
            if(!set.contains(i)){
    
                arr[index] = i;
                index++;
            }
        }
    }
    
    public int pick() {
    
       int i = random.nextInt(arr.length);
       return arr[i];


    }
}

Because the blacklist number is not repeated and is in [0,n) In this range , Here you can try use map Let's record [n-len,n) Interval data and will **[0,n-len)** Within the interval Blacklist Data mapped to **[n-len,n)** in be not in The blacklist On the number of In this way . The code is as follows ：

class Solution {
    

    private int n;
    private int[] blacklist;
    private int len;
    private Random random;
    private Map<Integer,Integer> map;

    public Solution(int n, int[] blacklist) {
    

        this.n = n;
        this.blacklist = blacklist;
        this.map = new HashMap();
        random = new Random();
        this.len = blacklist.length;
        for(int i =0;i < blacklist.length;i++){
    
            if(blacklist[i]>=n-len){
    
                map.put(blacklist[i],blacklist[i]);
            }
            
        }
        int end = n-1;
        int index = 0;
        for(int i = 0;i < blacklist.length;i++){
    
            int value = blacklist[i];
            if(value <n-len){
    
                while(map.containsKey(end)){
    
                    end--;
                }
                map.put(value,end);
                end--;
            }
        }
       
    }
    
    public int pick() {
    
       int i = random.nextInt(n-len);
       if(map.containsKey(i)){
    
           return map.get(i);
       }
       return i;

    }
}