710. random numbers in the blacklist

Original link ：710. Random numbers in the blacklist

 

solution:
        The title requires that a random one be returned 0 ~ n - 1 Numbers not on the blacklist , So we can 0 ~ n - 1 Divide into two groups .

        The first group is 0 ~ n - len - 1 and The second group n - len ~ n - 1  among len Indicates the number of numbers in the blacklist .

Use a hash table to create 0 ~ n - len - 1 In the blacklist count to n - len ~ n - 1 White list number mapping in .

class Solution {
public:
    int n,len;  //len Save the length of the blacklist 
    unordered_map<int,int> hash;    //hash Storage 0~n - len - 1 Medium blacklist number pairs n - len ~ n White list mapping in 
    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);    // preservation n - len ~ n In the white list 

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