algorithm - 生成一个从 0 到 N-1 的随机整数，该整数不在列表中

Question

给你 N和一个 int K[] .

手头的任务是在0 to N-1之间生成一个等概率随机数。这在 K 中不存在。

N严格来说是一个整数 >= 0 .和 K.length < N-1。和 0 <= K[i] <= N-1 .还假设 K 已排序并且 K 的每个元素都是唯一的。

给你一个函数 uniformRand(int M)它生成 0 to M-1 范围内的均匀随机数并假设此函数的复杂度为 O(1)。

例子:

N = 7

K = {0, 1, 5}

the function should return any random number { 2, 3, 4, 6 } with equal probability.

我可以为此得到一个 O(N) 的解决方案:首先生成一个介于 0 到 N - K.length 之间的随机数。并将由此生成的随机数映射到不在 K 中的数字。第二步将复杂度提高到 O(N)。可以在 O(log N) 中做得更好吗？

Answer 1

您可以利用 K[] 中的所有数字都在 0 和 N-1 之间并且它们不同这一事实。

对于您的示例，您生成一个从 0 到 3 的随机数。假设您得到一个随机数 r。现在对数组 K[] 进行二分查找。

初始化 i = K.length/2。

找到 K[i] - i。这将为您提供数组中 0 到 i 范围内缺失的数字数。

For example K[2] = 5. So 3 elements are missing from K[0] to K[2] (2,3,4)

因此您可以决定是否必须在数组 K 的第一部分或下一部分进行剩余搜索。这是因为您知道 r。

此搜索将为您提供 log(K.length) 的复杂度

编辑:例如，

N = 7

K = {0, 1, 4} // modified the array to clarify the algorithm steps.

the function should return any random number { 2, 3, 5, 6 } with equal probability.

1. 在 0 和 N-K.length 之间生成的随机数 = random{0-3}。假设我们得到 3。 因此我们需要数组 K 中第 4 个缺失的数字。

2. 对数组 K[] 进行二分查找。

   • 初始 i = K.length/2 = 1。

3. 现在我们看到 K[1] - 1 = 0。因此，在 i = 1 之前没有数字丢失。因此我们搜索数组的后半部分。

4. 现在 i = 2.K[2] - 2 = 4 - 2 = 2。因此，在索引 i = 2 之前，有 2 个缺失的数字。但是我们需要第四个缺失的元素。所以我们必须再次在数组的后半部分进行搜索。

5. 现在我们到达一个空数组。我们现在应该做什么？如果我们在 K[j] & K[j+1] 之间到达一个空数组，那么它只是意味着 K[j] 和 K 之间的所有元素数组 K 中缺少 [j+1]。

6. 因此 K[2] 以上的所有元素都从数组中丢失，即 5 和 6。我们需要 第 4 个元素，我们已经从中丢弃了 2 个元素。因此，我们将选择第二个元素，即 6。