# 710. Random Pick with Blacklist

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. `1 <= N <= 1000000000`
2. `0 <= B.length < min(100000, N)`
3. `[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:
Solution(int N, vector<int> blacklist) {
unordered_set<int> st;
len = N - blacklist.size();
for (int i = len; i < N; ++i) st.insert(i);
for (int num : blacklist) st.erase(num);
auto it = st.begin();
for (int num : blacklist) {
if (num < len) m[num] = *it++;
}
}

int pick() {
int k = rand() % len;
return m.count(k) ? m[k] : k;
}

private:
unordered_map<int, int> m;
int len;
};
``````

Random Pick with Weight

Random Pick Index

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

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation