710. Random Pick with Blacklist

• 710. Random Pick with Blacklist
  • Description
  • Intuition
    • Binary Search Solution
    • Remapping Solution
  • Pitfall
    • Binary Search Solution Pitfall
  • Solution
    • BinarySearch Solution
    • Remapping Solution

Description

Intuition

Binary Search Solution

If given a sorted blacklist, we can generate an integer k = [0, N - blacklist.length) and do a binary search to find the kth number

Remapping Solution

for example, N=10, blacklist=[3, 5, 8, 9]. In total, we only need to generate exclusive_upper_boundary ∈ [0, N - blacklist.length]

For any element in black list,

1. If elem >= exclusive_upper_bondary, discard
2. otherwise, we find one from the tail and mappint to that

Pitfall

Binary Search Solution Pitfall

B[mid] - mid indicates how many whitelist number less than B[mid]

也就是说

比7少的有7个，[0, 6]

Solution

BinarySearch Solution

private final int blacklist[], N;
  private final Random rand = new Random();

  public BinarySearchSolution(int N, int[] blacklist) {
    this.N = N;
    Arrays.sort(blacklist);
    this.blacklist = blacklist;
  }

  /**
   * Time complexity: O(log(B))
   * Space complexity: O(1)
   *
   * @return
   */
  public int pick() {
    final int target = rand.nextInt(N - blacklist.length);
    if (blacklist.length == 0) {
      return target;
    }

    // find the last <tt>mid</tt> < target,
    // result is <code>mid + blacklist[mid] + 1</code>
    int left = 0, right = blacklist.length - 1;

    while (left < right) {
      final int mid = left + (1 + right - left) / 2;
      if (blacklist[mid] - mid <= target) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    if (blacklist[left] - left > target) {
      return target;
    }
    return left + target + 1;
  }

Remapping Solution

  private final Random rand = new Random();
  private final int N;
  private final Map<Integer, Integer> map = new HashMap<>();

  public RemappingSolution(int N, int[] blacklist) {
    for (int i : blacklist) {
      map.put(i, -1);
    }
    this.N = N - blacklist.length;
    N--;
    for (int elem : blacklist) {
      if (elem < this.N) {
        while (map.containsKey(N)) {
          N--;
        }
        map.put(elem, N--);
      }
    }
  }

  public int pick() {
    final int i = rand.nextInt(N);
    return map.getOrDefault(i, i);
  }