LC710- 黑名单中的随机数

「link」

朴素解法：

把$[0,n-1]$集合中删除在黑名单$blackList$中的数字，得到剩余的白名单$whiteList$，每次$pick$就从白名单中取$whiteList[x]$，$x$为数组长度下的某个随机数。

但是这题的$n$的范围给到了$1e9$，在大数据范围下会$TLE$。

考虑到可以把$n$分为两个部分，前$n-blackLen$的部分记为白名单，后$blackLen$的部分记为黑名单。

于是再将前半部分的黑名单映射到后半部分的白名单即可。

因为根据推理可以得出若$[0,N-s)$内的元素，若有$i$个黑名单中，那么必有$[N-s,N)$中有$i$个元素为白名单。

JAVA 复制

class Solution {

    private int whiteEnd;
    private Random random;
    private Map<Integer, Integer> map;

    public Solution(int n, int[] blacklist) {
        // 存储黑名单区间中黑名单
        Set<Integer> blackSet = new HashSet<>();
        // 存储白名单区间中黑名单与黑名单区间中白名单的映射
        map = new HashMap<>();
        random = new Random();
        // 将[0, n)这个范围划为[0, whiteEnd)和[whiteEnd, n), 前者为白名单区间,后者为黑名单区间
        whiteEnd = n - blacklist.length;
        // 得到黑名单区间中黑名单
        for (int num : blacklist) {
            if (num >= whiteEnd) {
                blackSet.add(num);
            }
        }
        // 得到黑名单区间中的白名单
        List<Integer> whites = new ArrayList<>();
        for (int i = whiteEnd; i < n; i++) {
            if (!blackSet.contains(i)) {
                whites.add(i);
            }
        }
        // 将白名单区间中的黑名单与黑名单区间中的白名单做映射
        int idx = 0;
        for (int b : blacklist) {
            // b < whiteEnd就表示为白名单区间中的黑名单
            if (b < whiteEnd) {
                map.put(b, whites.get(idx++));
            }
        }
    }
    
    public int pick() {
        int idx = random.nextInt(whiteEnd);
        if (map.containsKey(idx)) {
            return map.get(idx);
        } else {
            return idx;
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */