题目描述
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 <= 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]
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.
题意:给一个数字N
和一个黑名单blackList
,我们需要生成一个[0,N)
之间的随机数并且这个随机数不在黑名单中。
算法1
(两次随机数)
题解1:刚开始我想的时将所有的白名单以区间的形式存储下来,然后,每次生成随机数的时候先随机选择一个区间再从这个区间随机选一个一个数。这样做的问题在于,没生成一个随机数,我们调用了两次随机数函数,而且每个数字的概率并不一样大。
C++ 代码
class Solution {
public:
vector<vector<int>> candidate;
int m;
Solution(int N, vector<int>& blacklist) {
int n = blacklist.size(),i = 0,cur = 0;
sort(blacklist.begin(),blacklist.end());
for(i = 0,cur = 0;i < n ; cur = blacklist[i] + 1,i ++)
{
if(blacklist[i] == cur)
{
while(i < n && blacklist[i] == cur)
{
cur ++;
i ++;
}
}
if(i != n)
candidate.push_back({cur,blacklist[i] - 1});
else
break;
}
if(cur < N)
candidate.push_back({cur,N - 1});
m = candidate.size();
}
int pick() {
int idx = rand() % m;
int l = candidate[idx][0],r = candidate[idx][1];
return rand() % (r - l + 1) + l;
}
};
算法2
(哈希表映射)
题解2:我们考虑这样一个事实,总共有N
个数字,黑名单中有n
个数。那么白名单中有N-n
个数字,那么我们只需要生成[0,N-n)
中的一个随机数就可以了,如果这个数字在黑名单当中,我们就把它映射到一个[n,N)
中一个白名单中的数字。基于上述思想,我们的算法如下:
- 先把所有的黑名单数字加入到哈希表中
- 遍历黑名单,如果黑名单的数字小于
N - n
,那么我们从N - 1
开始往前找一个不在黑名单中的并且没有被影射过的数字,改变这个黑名单数字的映射关系。 - 每次随机生成一个
[0,N-n)
之间的数字,如果这个数字在黑名单当中,那么返回哈希表中映射的数字,否则直接返回原来的数字就可以了。
C++ 代码
class Solution {
public:
unordered_map<int,int> hash;
int L,n,idx;
Solution(int N, vector<int>& blacklist) {
L = N,n = blacklist.size(),idx = N - 1;
for(int i = 0 ; i < n ; i ++)
hash[blacklist[i]] = -1;
sort(blacklist.begin(),blacklist.end());
for(int i = 0 ; i < n; i ++)
{
if(blacklist[i] >= N - n)
break;
while(hash.find(idx) != hash.end())
idx --;
hash[blacklist[i]] = idx --;
}
}
int pick() {
int res = rand() % (L - n);
if(hash.find(res) != hash.end())
return hash[res];
return res;
}
};
秒啊
alternative implementation