710. Random Pick with Blacklist

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

生成N内不出现在给定blacklist的随机数。实际有效长度len = N -blacklist.size()。如果让len外数字替换len内出现在blacklist的数字，然后以长度len作为新长度生成随机数，问题就解决了。 因此可以用一个额外的map记录下blacklist中在len内的坑对应len外合法的数字。

代码参考了这。直接用rand()%len来生成[0, len- 1]的随机数实际上是有点问题的，rand()是生成[0, RANDMAX)的随机数，假如RAND_MAX等于101，len = 100, 那101和1都会生成1，概率要比其他数高。

/*
 * @lc app=leetcode id=710 lang=cpp
 *
 * [710] Random Pick with Blacklist
 *
 * https://leetcode.com/problems/random-pick-with-blacklist/description/
 *
 * algorithms
 * Hard (32.01%)
 * Likes:    199
 * Dislikes: 46
 * Total Accepted:    8.2K
 * Total Submissions: 25.4K
 * Testcase Example:  '["Solution", "pick", "pick", "pick"]\n[[1, []], [], [], []]'
 *
 * Given a blacklist B containing unique integers from [0, N), write a function
 * to return a uniform random integer from [0, N) which is NOT in B.
 * 
 * Optimize it such that it minimizes the call to system’s Math.random().
 * 
 * Note:
 * 
 * 
 * 1 <= N <= 1000000000
 * 0 <= B.length < min(100000, N)
 * [0, N) does NOT include N. See interval notation.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: 
 * ["Solution","pick","pick","pick"]
 * [[1,[]],[],[],[]]
 * Output: [null,0,0,0]
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: 
 * ["Solution","pick","pick","pick"]
 * [[2,[]],[],[],[]]
 * Output: [null,1,1,1]
 * 
 * 
 * Example 3:
 * 
 * 
 * Input: 
 * ["Solution","pick","pick","pick"]
 * [[3,[1]],[],[],[]]
 * Output: [null,0,0,2]
 * 
 * 
 * Example 4:
 * 
 * 
 * Input: 
 * ["Solution","pick","pick","pick"]
 * [[4,[2]],[],[],[]]
 * Output: [null,1,3,1]
 * 
 * 
 * Explanation of Input Syntax:
 * 
 * The input is two lists: the subroutines called and their arguments.
 * Solution's constructor has two arguments, N and the blacklist B. pick has no
 * arguments. Arguments are always wrapped with a list, even if there aren't
 * any.
 * 
 */
class Solution {
public:
    unordered_map<int, int> m;
    int len; 
    Solution(int N, vector<int>& blacklist) {
        len = N - blacklist.size();
        unordered_set<int> st;
        // len外
        for (int i = len; i < N; ++i) {
            st.insert(i);
        }
        // 去掉blacklist中的
        for (const auto num : blacklist) st.erase(num);
        auto it = st.begin();
        for (const auto num : blacklist) {
            // 把len内blacklist中的数map到len外正常数
            if (num < len) m[num] = *it++;
        }
    }
    
    int pick() {
        int k = rand() % len;
        return m.count(k) ? m[k] : k;
    }
};

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