710. 黑名单中的随机数

原题链接：710. 黑名单中的随机数

 

solution:
        题目要求返回随机的一个0 ~ n - 1不在黑名单中的数字,因此可以把0 ~ n - 1分成两组。

        第一组为0 ~ n - len - 1 和 第二组 n - len ~ n - 1 其中len表示黑名单的数字个数.

利用哈希表建立0 ~ n - len - 1中黑名单数到n - len ~ n - 1中白名单数字的映射。

class Solution {
public:
    int n,len;  //len保存黑名单的长度
    unordered_map<int,int> hash;    //hash存储0~n - len - 1中黑名单数对n - len ~ n中白名单的映射
    Solution(int _n, vector<int>& blacklist) {
        n = _n;
        len = blacklist.size();
        unordered_set<int> s;
        for(int i = n - len;i < n;i++) s.insert(i); 
        for(auto &x : blacklist) s.erase(x);    //保存n - len ~ n中白名单

        //建立映射
        auto it = s.begin();
        for (auto x: blacklist)
            if (x < n - len)
                hash[x] = *it ++ ;
    }
    
    int pick() {
        int x = rand() % (n - len);
        if(hash.count(x)) return hash[x];
        return x;
    }
};

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