710. 黑名单中的随机数

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

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

实现 Solution 类:

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

示例 1：

输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

提示:

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

/保证0-wsize 都是白名单，如果里面有黑名单的映射到wsize-n的白名单中
//遍历两次黑名单，

class Solution {
public:
    Solution(int n, vector& blacklist) {
        sort(blacklist.begin(), blacklist.end());
        total = n;
        bSize = blacklist.size();
        wSize = total - bSize;
        for (auto it : blacklist)
        {
            if (it >= wSize)
            {
                bMap[it] = it;
            }
        }
        int index = wSize;
        while (bMap.count(index) > 0)
        {
            index++;
        }
        for (int i = 0; i < blacklist.size();i++)
        {
            if (blacklist[i] >= wSize)
            {
                break;
            }
            wMap[blacklist[i]] = index;
            index++;
            while (bMap.count(index) > 0)
            {
                index++;
            }
        }    
    }

    int pick() 
    {
        int num = rand() % wSize;
        if (wMap.size() >0 )
        {
            num = wMap.count(num)>0 ? wMap[num] : num;
        }
        return num;
    }
private:
    mapbMap;
    mapwMap;
    int bSize;
    int total;
    int wSize;
};