黑名单中的随机数

题目描述：

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

示例 1：

输入
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

提示:

1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] < n
blacklist 中所有值都 不同
pick 最多被调用 2 * 104 次

思路:

时间复杂度：O(n),空间复杂度O(n)

用映射，把n-m的黑数映射到后面

代码:

type Solution struct {
    bound int
    b2w map[int]int
}


func Constructor(n int, blacklist []int) Solution {
    black := make(map[int]bool,0)
    m := len(blacklist)
    bound := n-m
    for _,v :=range blacklist{
        if v >= bound{
            black[v] = true
        }
    }
    w := bound
    b2w := make(map[int]int, m-len(black))
    for _,b := range blacklist{
        if b < bound{
            for black[w]{
                w++
            }
            b2w[b] = w
            w++
        }
    }
    return Solution{bound,b2w}

}


func (this *Solution) Pick() int {
    x := rand.Intn(this.bound)
     if this.b2w[x] > 0 {
        return this.b2w[x]
    }
    return x
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(n, blacklist);
 * param_1 := obj.Pick();
 */

代码效率：

执行用时：92 ms, 在所有 Go 提交中击败了92.31%的用户
内存消耗：11.7 MB, 在所有 Go 提交中击败了38.46%的用户