README_EN.md

710. Random Pick with Blacklist

中文文档

Description

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:

<li><code>1 &lt;= N &lt;= 1000000000</code></li>

<li><code>0 &lt;= B.length &lt; min(100000, N)</code></li>

<li><code>[0, N)</code>&nbsp;does NOT include N. See <a href="https://en.wikipedia.org/wiki/Interval_(mathematics)" target="_blank">interval notation</a>.</li>

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.

Solutions

Python3

Java

...