710. 黑名单中的随机数

看了下leetcode的每日一题，题目链接：710. 黑名单中的随机数
题目描述如下：

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数 int
pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

提示:

1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <=blacklist[i] < n
blacklist 中所有值都 不同
pick 最多被调用 2 * 104 次

看到这道题的第一思路是 将不在黑名单的数据放到一个新的数据中，再随机取一个数，但提交却发现空间，超过内存限制，代码如下：

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];


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

由于黑名单数不重复且在[0,n)这个区间内，这里可以试试 用map来记录一下 [n-len,n) 区间的数据并将 **[0,n-len)**区间内在 黑名单中 的数据映射到 **[n-len,n)**中 不在 黑名单 的数上 这个方式解决。代码如下：

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;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45