0710. Random Pick With Blacklist

# 710. Random Pick with Blacklist#

## 题目 #

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. 1 <= N <= 1000000000
2. 0 <= B.length < min(100000, N)
3. [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.

## 解题思路 #

hash 表总长度应该为 M = N - len(backlist)，然后在 M 的长度中扫描是否有在黑名单中的数，如果有，就代表 hash 冲突了。冲突就把这个数字映射到 (M,N) 这个区间范围内。为了提高效率，可以选择这个区间的头部或者尾部开始映射，我选择的是末尾开始映射。从 (M,N) 这个区间的末尾开始往前找，找黑名单不存在的数，找到了就把 [0,M] 区间内冲突的数字映射到这里来。最后 pick 的时候，只需要查看 map 中是否存在映射关系，如果存在就输出 map 中映射之后的值，如果没有就代表没有冲突，直接输出那个 index 即可。

## 代码 #

``````
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();
*/

``````

Apr 8, 2023