|
看了下leetcode的每日一题，题目链接：710. 黑名单中的随机数
题目描述如下：
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数 int
pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
提示:
1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <=blacklist[i] < n
blacklist 中所有值都 不同
pick 最多被调用 2 * 104 次
看到这道题的第一思路是 将不在黑名单的数据放到一个新的数据中，再随机取一个数，但提交却发现空间，超过内存限制，代码如下：
class Solution {
private int n;
private int[] blacklist;
private Set<Integer> set;
private int[] arr;
private int len;
private Random random = new Random();
public Solution(int n, int[] blacklist) {
this.n = n;
this.blacklist = blacklist;
this.set = new HashSet();
this.len = blacklist.length;
this.arr = new int[n-len];
for(int i =0;i < blacklist.length;i++){
set.add(blacklist[i]);
}
int index = 0;
for(int i = 0;index < arr.length;i++){
if(!set.contains(i)){
arr[index] = i;
index++;
}
}
}
public int pick() {
int i = random.nextInt(arr.length);
return arr[i];
}
}
由于黑名单数不重复且在[0,n)这个区间内，这里可以试试 用map来记录一下 [n-len,n) 区间的数据并将 **[0,n-len)**区间内在 黑名单中 的数据映射到 **[n-len,n)**中 不在 黑名单 的数上 这个方式解决。代码如下：
class Solution {
private int n;
private int[] blacklist;
private int len;
private Random random;
private Map<Integer,Integer> map;
public Solution(int n, int[] blacklist) {
this.n = n;
this.blacklist = blacklist;
this.map = new HashMap();
random = new Random();
this.len = blacklist.length;
for(int i =0;i < blacklist.length;i++){
if(blacklist[i]>=n-len){
map.put(blacklist[i],blacklist[i]);
}
}
int end = n-1;
int index = 0;
for(int i = 0;i < blacklist.length;i++){
int value = blacklist[i];
if(value <n-len){
while(map.containsKey(end)){
end--;
}
map.put(value,end);
end--;
}
}
}
public int pick() {
int i = random.nextInt(n-len);
if(map.containsKey(i)){
return map.get(i);
}
return i;
}
}
|