710. Random Pick with Blacklist (H)

https://leetcode.com/problems/random-pick-with-blacklist/

You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely to be returned.

Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language.

Implement the Solution class:

• Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.

• int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.

Example 1:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

Explanation
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // return 0, any integer from [0,1,4,6] should be ok. Note that for every call of pick,
                 // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4).
solution.pick(); // return 4
solution.pick(); // return 1
solution.pick(); // return 6
solution.pick(); // return 1
solution.pick(); // return 0
solution.pick(); // return 4

Constraints:

• 1 <= n <= 109

• 0 <= blacklist.length <- min(105, n - 1)

• 0 <= blacklist[i] < n

• All the values of blacklist are unique.

• At most 2 * 104 calls will be made to pick.

Solution:

710-random-pick-with-blacklist · Leetcode Notesjust4once.gitbooks.io

Version 2:

pick 函数会被多次调用，每次调用都要在区间 [0,N) 中「等概率随机」返回一个「不在 blacklist 中」的整数。

这应该不难理解吧，比如给你输入 N = 5, blacklist = [1,3]，那么多次调用 pick 函数，会等概率随机返回 0, 2, 4 中的某一个数字。

而且题目要求，在 pick 函数中应该尽可能少调用随机数生成函数 rand()。

这句话什么意思呢，比如说我们可能想出如下拍脑袋的解法：

int pick() {
    int res = rand() % N;
    while (res exists in blacklist) {
        // 重新随机一个结果
        res = rand() % N;
    }
    return res;
}

这个函数会多次调用 rand() 函数，执行效率竟然和随机数相关，不是一个漂亮的解法。

聪明的解法类似上一道题，我们可以将区间 [0,N) 看做一个数组，然后将 blacklist 中的元素移到数组的最末尾，同时用一个哈希表进行映射：

根据这个思路，我们可以写出第一版代码（还存在几处错误）：

class Solution {
public:
    int sz;
    unordered_map<int, int> mapping;
    
    Solution(int N, vector<int>& blacklist) {
        // 最终数组中的元素个数
        sz = N - blacklist.size();
        // 最后一个元素的索引
        int last = N - 1;
        // 将黑名单中的索引换到最后去
        for (int b : blacklist) {
            mapping[b] = last;
            last--;
        }
    }
};

如上图，相当于把黑名单中的数字都交换到了区间 [sz, N) 中，同时把 [0, sz) 中的黑名单数字映射到了正常数字。

根据这个逻辑，我们可以写出 pick 函数：

int pick() {
    // 随机选取一个索引
    int index = rand() % sz;
    // 这个索引命中了黑名单，
    // 需要被映射到其他位置
    if (mapping.count(index)) {
        return mapping[index];
    }
    // 若没命中黑名单，则直接返回
    return index;
}

这个 pick 函数已经没有问题了，但是构造函数还有两个问题。

第一个问题，如下这段代码：

int last = N - 1;
// 将黑名单中的索引换到最后去
for (int b : blacklist) {
    mapping[b] = last;
    last--;
}

我们将黑名单中的 b 映射到 last，但是我们能确定 last 不在 blacklist 中吗？

比如下图这种情况，我们的预期应该是 1 映射到 3，但是错误地映射到 4：

在对 mapping[b] 赋值时，要保证 last 一定不在 blacklist 中，可以如下操作：

// 构造函数
Solution(int N, vector<int>& blacklist) {
    sz = N - blacklist.size();
    // 先将所有黑名单数字加入 map
    for (int b : blacklist) { 
        // 这里赋值多少都可以
        // 目的仅仅是把键存进哈希表
        // 方便快速判断数字是否在黑名单内
        mapping[b] = 666;
    }

    int last = N - 1;
    for (int b : blacklist) {
        // 跳过所有黑名单中的数字
        while (mapping.count(last)) {
            last--;
        }
        // 将黑名单中的索引映射到合法数字
        mapping[b] = last;
        last--;
    }
}

第二个问题，如果 blacklist 中的黑名单数字本身就存在区间 [sz, N) 中，那么就没必要在 mapping 中建立映射，比如这种情况：

我们根本不用管 4，只希望把 1 映射到 3，但是按照 blacklist 的顺序，会把 4 映射到 3，显然是错误的。

我们可以稍微修改一下，写出正确的解法代码：

class Solution {
public:
    int sz;
    unordered_map<int, int> mapping;
    
    Solution(int N, vector<int>& blacklist) {
        sz = N - blacklist.size();
        for (int b : blacklist) {
            mapping[b] = 666;
        }

        int last = N - 1;
        for (int b : blacklist) {
            // 如果 b 已经在区间 [sz, N)
            // 可以直接忽略
            if (b >= sz) {
                continue;
            }
            while (mapping.count(last)) {
                last--;
            }
            mapping[b] = last;
            last--;
        }
    }

    // 见上文代码实现
    int pick() {}
};

至此，这道题也解决了，总结一下本文的核心思想：

1、如果想高效地，等概率地随机获取元素，就要使用数组作为底层容器。

2、如果要保持数组元素的紧凑性，可以把待删除元素换到最后，然后 pop 掉末尾的元素，这样时间复杂度就是 O(1) 了。当然，我们需要额外的哈希表记录值到索引的映射。

3、对于第二题，数组中含有「空洞」（黑名单数字），也可以利用哈希表巧妙处理映射关系，让数组在逻辑上是紧凑的，方便随机取元素。

JAVA Version:

HashMap Remapping

1. Split these N numbers into two parts from 0 to N - M - 1 and from N - M to N - 1

2. Now, we remap the blacklisted numbers on the left part to the white ones

   1. Find all the white numbers on the right

   2. Loop through the blacklist and remap the number that are less than N - M to the numbers above

3. We can simply generate an random number and pick from the map, and return the default k if it's not present in the map

4. Time complexity O(B)

5. Space complexity O(B)

class Solution {
    private Random random;
    private Map<Integer, Integer> map;
    private int L;
    public Solution(int N, int[] blacklist) {
        this.random = new Random();
        this.map = new HashMap<>();
        this.L = N - blacklist.length;
        Set<Integer> set = new HashSet<>();
        for (int i = L; i < N; i++) set.add(i);
        for (int b : blacklist) set.remove(b);
        Iterator<Integer> it = set.iterator();
        for (int b : blacklist) {
            if (b < L) {
                map.put(b, it.next());
            }
        }
    }

    public int pick() {
        int k = random.nextInt(L);
        return map.getOrDefault(k, k);
    }
}