Question

710. 黑名单中的随机数

English Version

题目描述

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

• Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
• int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

 

示例 1：

输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
         // 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

 

提示:

• 1 <= n <= 109
• 0 <= blacklist.length <= min(105, n - 1)
• 0 <= blacklist[i] < n
• blacklist 中所有值都 不同
•  pick 最多被调用 2 * 104 次

解法

方法一：哈希表

class Solution:
  def __init__(self, n: int, blacklist: List[int]):
    self.k = n - len(blacklist)
    self.d = {}
    i = self.k
    black = set(blacklist)
    for b in blacklist:
      if b < self.k:
        while i in black:
          i += 1
        self.d[b] = i
        i += 1

  def pick(self) -> int:
    x = randrange(self.k)
    return self.d.get(x, x)


# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()

class Solution {
  private Map<Integer, Integer> d = new HashMap<>();
  private Random rand = new Random();
  private int k;

  public Solution(int n, int[] blacklist) {
    k = n - blacklist.length;
    int i = k;
    Set<Integer> black = new HashSet<>();
    for (int b : blacklist) {
      black.add(b);
    }
    for (int b : blacklist) {
      if (b < k) {
        while (black.contains(i)) {
          ++i;
        }
        d.put(b, i++);
      }
    }
  }

  public int pick() {
    int x = rand.nextInt(k);
    return d.getOrDefault(x, x);
  }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */

class Solution {
public:
  unordered_map<int, int> d;
  int k;

  Solution(int n, vector<int>& blacklist) {
    k = n - blacklist.size();
    int i = k;
    unordered_set<int> black(blacklist.begin(), blacklist.end());
    for (int& b : blacklist) {
      if (b < k) {
        while (black.count(i)) ++i;
        d[b] = i++;
      }
    }
  }

  int pick() {
    int x = rand() % k;
    return d.count(x) ? d[x] : x;
  }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(n, blacklist);
 * int param_1 = obj->pick();
 */

type Solution struct {
  d map[int]int
  k int
}

func Constructor(n int, blacklist []int) Solution {
  k := n - len(blacklist)
  i := k
  black := map[int]bool{}
  for _, b := range blacklist {
    black[b] = true
  }
  d := map[int]int{}
  for _, b := range blacklist {
    if b < k {
      for black[i] {
        i++
      }
      d[b] = i
      i++
    }
  }
  return Solution{d, k}
}

func (this *Solution) Pick() int {
  x := rand.Intn(this.k)
  if v, ok := this.d[x]; ok {
    return v
  }
  return x
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(n, blacklist);
 * param_1 := obj.Pick();
 */