[LeetCode]Random Pick with Blacklist

假设blacklist的size为k，这道题第一个想法应该就是把所有不在blacklist里的数字重新map到[0, N - k)，的区间中。这样我们只需要生成一个在[0, N- k)范围中的数然后找对于map的原来的数字即可。但是鉴于这道题输入的范围，N可以达到10^9，我们是不可能开出这么大的数组的，所以我们要想其他的办法。
第一个想法就是时间换空间，既然没有那么多空间，我们在pick()多花点时间即可，比如我们可以生成一个[0, N - k)的数i，然后找第i个不在blacklist里的数返回。但是这样的话显然每次pick的时间复杂度变为了O(N)，这是我们不能接受的。
有的时候我们需要从另一个角度思考，既然我们存不下N的范围，k的范围我们总是可以存的下的。对于生成的在[0, N - k)中的数i，其可能在blacklist当中，但是如果对于所有在[0, N - k)范围中并且在blacklist当中的数，我们重新map到[N - k, N)范围中另一个不在blacklist的数(显然这两个集合的size是相等的，我们可以做到一一映射)。我们仍然可以达到我们之前所说的效果，并且这个在空间上是完全可行的。
时间复杂度的话，我们要对blacklist进行sort，所以constructor的时间复杂度为O(N * log N)，pick的话为O(1)。空间复杂度O(k)。代码如下：