random pick with blacklist

leetcode地址

type Solution struct {
    n int
    m map[int]int
}

func Constructor(N int, blacklist []int) Solution {
    nn := N - len(blacklist)
    m := make(map[int]int, len(blacklist))
    bm := make(map[int]int, len(blacklist))
    am := make(map[int]int, len(blacklist))
    for i := range blacklist {
        v := blacklist[i]
        if v < nn {
            bm[v] = 0
        }
        am[v] = 0
    }
    i := nn
    for bi := range bm {
        _, has := am[i]
        for has {
            i++
            _, has = am[i]
        }
        m[bi] = i
        i++
    }
    return Solution{
        n: nn,
        m: m,
    }
}

func (this *Solution) Pick() int {
    r := rand.Intn(this.n)
    if v, has := this.m[r]; has {
        return v
    }
    return r
}

Runtime: 152 ms, faster than 100.00% of Go online submissions for Random Pick with Blacklist.