Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
710. Random Pick with Blacklist.go
710. Random Pick with Blacklist_test.go
README.md

README.md

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.

题目大意

给一个数字 N,再给一个黑名单 B,要求在 [0,N) 区间内随机输出一个数字,这个是不在黑名单 B 中的任意一个数字。

解题思路

这道题的 N 的范围特别大,最大是 10 亿。如果利用桶计数,开不出来这么大的数组。考虑到题目要求我们输出的数字是随机的,所以不需要存下所有的白名单的数字。

假设 N=10, blacklist=[3, 5, 8, 9]

这一题有点类似 hash 冲突的意思。如果随机访问一个数,这个数正好在黑名单之内,那么就 hash 冲突了,我们就把它映射到另外一个不在黑名单里面的数中。如上图,我们可以将 3,5 重新映射到 7,6 的位置。这样末尾开始的几个数要么是黑名单里面的数,要么就是映射的数字。

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

You can’t perform that action at this time.