LeetCode: 710. Random Pick with Blacklist

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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 ⇐ N ⇐ 1000000000
0 ⇐ B.length < min(100000, N)
[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.

思路分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-05 22:30:53
 */
class Solution {
  Map<Integer, Integer> b2w;
  Random random;
  int size;

  /**
   * 把黑名单都放在最后
   */
  public Solution(int n, int[] blacklist) {
    size = n - blacklist.length;
    random = new Random();
    b2w = new HashMap<>();
    List<Integer> sb = new ArrayList<>();
    List<Integer> bw = new ArrayList<>();
    Set<Integer> bb = new HashSet<>();
    for (int i = 0; i < blacklist.length; i++) {
      int b = blacklist[i];
      // 按照界限，把黑名单数字按照大小分开
      if (b >= size) {
        bb.add(b);
      } else {
        sb.add(b);
      }
    }
    for (int i = n - 1; i >= size; i--) {
      // 从最后的数字里找出不是黑名单的数字
      if (!bb.contains(i)) {
        bw.add(i);
      }
    }
    // 建立起黑→白的对应关系
    while (!sb.isEmpty() && !bw.isEmpty()) {
      Integer b = sb.remove(sb.size() - 1);
      Integer w = bw.remove(bw.size() - 1);
      b2w.put(b, w);
    }
  }

  public int pick() {
    int val = random.nextInt(size);
    return b2w.getOrDefault(val, val);
  }
}