-
Notifications
You must be signed in to change notification settings - Fork 0
/
No710RandomPickWithBlacklist.java
51 lines (44 loc) · 1.38 KB
/
No710RandomPickWithBlacklist.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package com.wzx.leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
* @see <a href="https://leetcode.com/problems/random-pick-with-blacklist/">https://leetcode.com/problems/random-pick-with-blacklist/</a>
* @author wzx
*/
public class No710RandomPickWithBlacklist {
/**
* 连续存储能做到O(1)等概率随机
* 利用map映射, 将不在黑名单的元素集中到前N-blacklist中
*/
public static class Solution {
private final Map<Integer, Integer> black2sz;
private final Random random = new Random();
private final int size;
public Solution(int N, int[] blacklist) {
black2sz = new HashMap<>();
// 建立blacklist的hashset
for (int black : blacklist) {
black2sz.put(black, -1);
}
size = N - blacklist.length;
int last = N - 1;
for (int black : blacklist) {
// 将在N-blacklist内的黑名单元素映射为N-blacklist外的非黑名单元素
if (black <= size - 1) {
// 找到N-blacklist外的非黑名单元素
while (black2sz.containsKey(last)) {
last--;
}
black2sz.put(black, last);
last--;
}
}
}
public int pick() {
int rand = random.nextInt(size);
// 如果不在blacklist直接返回, 否则进行映射
return black2sz.getOrDefault(rand, rand);
}
}
}