710. Random Pick with Blacklist #
Problem #
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.
Problem Summary #
Given a number N, and then a blacklist B, randomly output a number within the interval [0,N); this is any number that is not in the blacklist B.
Solution Approach #
The range of N in this problem is especially large, up to 1 billion. If bucket counting is used, an array that large cannot be allocated. Considering that the problem requires us to output a random number, there is no need to store all the whitelist numbers.
Assume N=10, blacklist=[3, 5, 8, 9]
This problem is somewhat similar to the idea of hash collisions. If a randomly accessed number happens to be in the blacklist, then a hash collision occurs, and we map it to another number that is not in the blacklist. As shown above, we can remap 3 and 5 to the positions of 7 and 6. In this way, the last few numbers are either numbers in the blacklist or mapped numbers.
The total length of the hash table should be M = N - len(backlist). Then scan within the length M to see whether there are numbers in the blacklist; if there are, it represents a hash collision. For a collision, map this number to the interval (M,N). To improve efficiency, you can choose to start mapping from the head or the tail of this interval; I choose to start from the end. Starting from the end of the interval (M,N), search backward for a number that does not exist in the blacklist. Once found, map the conflicting number in the interval [0,M] to it. Finally, when picking, you only need to check whether a mapping relationship exists in the map. If it exists, output the value after mapping in the map; if not, it means there is no collision, so directly output that index.
Code #
package leetcode
import "math/rand"
type Solution struct {
M int
BlackMap map[int]int
}
func Constructor710(N int, blacklist []int) Solution {
blackMap := map[int]int{}
for i := 0; i < len(blacklist); i++ {
blackMap[blacklist[i]] = 1
}
M := N - len(blacklist)
for _, value := range blacklist {
if value < M {
for {
if _, ok := blackMap[N-1]; ok {
N--
} else {
break
}
}
blackMap[value] = N - 1
N--
}
}
return Solution{BlackMap: blackMap, M: M}
}
func (this *Solution) Pick() int {
idx := rand.Intn(this.M)
if _, ok := this.BlackMap[idx]; ok {
return this.BlackMap[idx]
}
return idx
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(N, blacklist);
* param_1 := obj.Pick();
*/
中文