Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/710.html
710. Random Pick with Blacklist
Level
Hard
Description
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]
Example 4:
Input:
[“Solution”,”pick”,”pick”,”pick”]
[[4,[2]],[],[],[]]
Output: [null,1,3,1]
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.
Solution
Given an integer N
and a blacklist B
, there are N - B.length
numbers that can be selected. For example, if N
is 100 and B.length
is 10, then there are 100 - 10 = 90 numbers that can be selected. Therefore, call Math.random()
so that the returned integer is in the range [0, N - B.length)
.
For each number in the blacklist, it is either less than N - B.length
or greater than or equal to N - B.length
. If a number in the blacklist is less than N - B.length
, then it should be mapped to a number in the range [N - B.length, N)
which is not in the blacklist.
In the class, maintain size
which is the number of integers that can be selected, maintain a set to store the numbers in the blacklist, and maintain a map.
For the constructor, initialize size = N - B.length
, and add all the numbers in the blacklist to the set. Then for each number in the blacklist, map it to num
which is in the range [size, N)
and is not in the blacklist (num
is updated after each mapping), with the map updated.
For the method pick
, randomly select an integer in the range [0, size)
, get the corresponding integer from the map (if the integer is not in the map, then the integer remains unchanged), and return the integer.
-
class Solution { int size; Set<Integer> blacklistSet; Map<Integer, Integer> map; public Solution(int N, int[] blacklist) { size = N - blacklist.length; blacklistSet = new HashSet<Integer>(); for (int blacklistNum : blacklist) blacklistSet.add(blacklistNum); map = new HashMap<Integer, Integer>(); int num = size; for (int blacklistNum : blacklist) { if (blacklistNum < size) { while (blacklistSet.contains(num)) num++; map.put(blacklistNum, num); num++; } } } public int pick() { int num = (int) (Math.random() * size); num = map.getOrDefault(num, num); return num; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(N, blacklist); * int param_1 = obj.pick(); */
-
// OJ: https://leetcode.com/problems/random-pick-with-blacklist/ // Time: // Solution: O(BlogB) // pick: O(1) // Space: O(B) class Solution { unordered_map<int, int> m; int len; public: Solution(int n, vector<int>& B) { len = n - B.size(); sort(begin(B), end(B)); int j = lower_bound(begin(B), end(B), len) - begin(B), N = B.size(), next = len; for (int i = 0; i < N && B[i] < len; ++i) { while (j < N && B[j] == next) ++j, ++next; m[B[i]] = next++; } } int pick() { int r = rand() % len; return m.count(r) ? m[r] : r; } };
-
class Solution: def __init__(self, n: int, blacklist: List[int]): self.k = n - len(blacklist) self.d = {} i = self.k black = set(blacklist) for b in blacklist: if b < self.k: while i in black: i += 1 self.d[b] = i i += 1 def pick(self) -> int: x = randrange(self.k) return self.d.get(x, x) # Your Solution object will be instantiated and called as such: # obj = Solution(n, blacklist) # param_1 = obj.pick()
-
type Solution struct { d map[int]int k int } func Constructor(n int, blacklist []int) Solution { k := n - len(blacklist) i := k black := map[int]bool{} for _, b := range blacklist { black[b] = true } d := map[int]int{} for _, b := range blacklist { if b < k { for black[i] { i++ } d[b] = i i++ } } return Solution{d, k} } func (this *Solution) Pick() int { x := rand.Intn(this.k) if v, ok := this.d[x]; ok { return v } return x } /** * Your Solution object will be instantiated and called as such: * obj := Constructor(n, blacklist); * param_1 := obj.Pick(); */