710. 黑名单中的随机数.md

710. 黑名单中的随机数

题目传送门

点击这里

解题思路

这道题难在于对于黑名单内容和给定范围内的数字的关系处理，很多人能想到使用hash来做，但是真的每次hash用一个新的数组范围来进行随机返回会很浪费时间和空间。这里最好的方法是用一个hash映射关系，假设我们黑名单的长度为m，那么在0~n-1范围内，就有n-m个白名单，如果我们将在[0, n-m)范围内的黑名单，用[n-m, n-1]范围内的白名单来替换，就可以做到在[0, n-m)范围内的随机等概率返回了。

代码

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

func Constructor(n int, blacklist []int) Solution {
	m := len(blacklist)
	// n-m个白名单
	bound := n - m
	black := map[int]bool{}
	for _, b := range blacklist {
		// 如果是在[n-m,n-1]这个范围内的，不需要做映射
		if b >= bound {
			black[b] = true
		}
	}
	// 其他的要做映射
	b2w := make(map[int]int, m-len(black))
	w := bound
	for _, b := range blacklist {
		// 在[0,n-m)范围内的黑名单数字
		if b < bound {
			// 一直循环w，直到w不是黑名单成员
			for black[w] {
				w++
			}
			// 映射
			b2w[b] = w
			w++
		}
	}
	return Solution{b2w, bound}
}

func (s *Solution) Pick() int {
	x := rand.Intn(s.bound)
	// 如果是在[0,n-m)内的黑名单成员，则返回映射中的白名单
	if s.b2w[x] > 0 {
		return s.b2w[x]
	}
	return x
}