Q56 Random Pick with Blacklist - LeetCode
Wed Feb 01 2023 06:15:04 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
HashMap<Integer,Integer> map;
Random r;
int top;
public Solution(int n, int[] blacklist) {
this.map = new HashMap<>();
this.r = new Random();
this.top = n - blacklist.length;
HashSet<Integer> set = new HashSet<>();
//adding all blacklist integers to set
for(int i =0 ; i< blacklist.length;i++)
set.add(blacklist[i]);
n--; //as range is 0 to n-1;
for(int i = 0 ;i < blacklist.length ; i++){
//if we have a bl element < top
if(blacklist[i] < top){
//if the element to be mapped is also bl element move back
while(set.contains(n))
n--;
//map to non bl element and move back
map.put(blacklist[i],n);
n--;
}
}
}
public int pick() {
int ridx = r.nextInt(top); //gives random b/w 0 to top-1, top is exclusive
//if its a mapped element
if(map.containsKey(ridx))
return map.get(ridx);
return ridx;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(n, blacklist);
* int param_1 = obj.pick();
*/
content_copyCOPY
https://leetcode.com/problems/random-pick-with-blacklist/
Comments