LC710- 黑名单中的随机数

「link」

朴素解法：

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

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

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

image.png

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

image.png

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

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();
 */