刷题记录第五十一天-黑名单中的随机数

题目描述如下：
给定一个整数n和一个整数黑名单balcklist，目标是写一个随机函数，随机从(0,n-1)中选择一个不属于黑名单里的数，且每个数被取得的概率相同。
思路如下：

1. 假设用rand()函数从[ 0,n-balcklist.size() )中随机取一个数，那么取到的数可能是黑名单里的数。
2. 假设黑名单里有k个数在[0,size())里，那么就有k个不属于黑名单的数在[size,n-1)里。
3. 我们只需要用一个map，将[0,size())中属于黑名单的数一一映射成[size,n-1)中非黑名单数即可。
4. 最后，利用rand()%size得到的数如果属于黑名单就返回map映射，否则就返回这个数

class Solution {
public:
    int size;
    unordered_map<int,int> map;
    Solution(int n, vector<int>& blacklist) {
        for(int i:blacklist){
            map[i]=1;
        }
        size = n-blacklist.size();
        int last = n-1;
        for(int num:blacklist){
            if(num>=size)
                continue;
            while(map.count(last)!=0){
                last--;
            }
            map[num]=last;
            last--;
        }
    }
    
    int pick() {
        int num=rand()%size;
        if(map.count(num)!=0){
            return map[num];
        }
        return num;
    }
};