力扣 710. 黑名单中的随机数

题目来源：https://leetcode.cn/problems/random-pick-with-blacklist/

大致题意：
给定一个数字范围 n，一个黑名单数组，设计一个类返回 0 到 n - 1 之间不在黑名单中的随机数，要求每个数被返回的概率应该相等

思路

设黑名单数组长度为 m，那么返回数字的个数有 n - m 个

所以可以设置随机数的 bound 为 n - m

• 若黑名单中的数都大于等于 bound，那么不用做任何处理
• 若黑名单中的数有小于 bound，可以使用哈希表将其映射到 [bound, n - 1] 中。这样在随机数生成器生成黑名单中小于 bound 的数时，直接映射到另一个数即可

代码：

public class Pick {
    
    // 映射黑名单小于 bound 的数
    Map<Integer, Integer> map;
    int bound;
    Random random;

    public Pick(int n, int[] blacklist) {
    
        map = new HashMap<>();
        int m = blacklist.length;
        // 初始化 bound
        bound = n - m;
        random = new Random();
        // 存黑名单数字的哈希表
        Set<Integer> blackSet = new HashSet<>();
        for (int num : blacklist) {
    
            if (num >= bound) {
    
                blackSet.add(num);
            }
        }
        // 映射索引
        int idx = bound;
        // 遍历黑名单
        for (int num : blacklist) {
    
            // 若该黑名单数字小于 bound，将其映射为 [bound, n - 1] 中不在黑名单且还未被映射的数
            if (num < bound) {
    
                // 若当前要映射的数在黑名单中，索引 +1
                while (blackSet.contains(idx)) {
    
                    idx++;
                }
                map.put(num, idx++);
            }
        }
    }

    public int pick() {
    
        // 生成随机数
        int x = random.nextInt(bound);
        // 返回随机数，若随机数在 map 中，返回其映射的数字
        return map.getOrDefault(x, x);
    }

}