-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
701.java
101 lines (93 loc) · 2.8 KB
/
701.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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
__________________________________________________________________________________________________
sample 87 ms submission
class Solution {
Random random;
HashMap<Integer, Integer> mp;
ArrayList<Integer> arr;
int n ; int pointer;
public Solution(int N, int[] blacklist) {
random = new Random(123456734567L);
arr = new ArrayList<Integer>();
mp = new HashMap<>();
for(int i = 0 ; i < blacklist.length; i++)
mp.putIfAbsent(blacklist[i], 0 );
n = N;
pointer = 0;
}
public int pick() {
if(pointer == n)pointer = 0 ;
if(mp.size() > n - mp.size()){
if(arr.size() == 0){
for(int i = 0 ; i < n ; i++)if(!mp.containsKey(i)){arr.add(i);}
}
for(int i = pointer ; i < arr.size() ; i++){
pointer = i+1;
return arr.get(i);
}
for(int i = 0 ; i < pointer; i++){
pointer = i+1;
return arr.get(i);
}
}
if(pointer == n)pointer = 0 ;
for(int i = pointer ; i < n; i++){
if(!mp.containsKey(i)){
pointer = i+1;
return i;
}
}
for(int i = 0 ; i < pointer; i++){
if(!mp.containsKey(i)){
pointer = i+1;
return i;
}
}
return -1;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(N, blacklist);
* int param_1 = obj.pick();
*/
__________________________________________________________________________________________________
sample 53204 kb submission
class Solution {
// N: [0, N)
// B: blacklist
// B1: < N
// B2: >= N
// M: N - B1
int M;
Random r;
Map<Integer, Integer> map;
public Solution(int N, int[] blacklist) {
map = new HashMap();
for (int b : blacklist) // O(B)
map.put(b, -1);
M = N - map.size();
for (int b : blacklist) { // O(B)
if (b < M) { // re-mapping
while (map.containsKey(N - 1))
N--;
//Important to note this remapping using values
//Suppose N=10, blacklist=[3, 5, 8, 9], re-map 3 and 5 to 7 and 6
map.put(b, N - 1);
N--;
}
}
r = new Random();
}
public int pick() {
int p = r.nextInt(M);
if (map.containsKey(p))
return map.get(p);
return p;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(N, blacklist);
* int param_1 = obj.pick();
*/
__________________________________________________________________________________________________