生成从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}

该函数应以相同的概率返回任意随机数{2,3,4,6}.

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

Answer 1

你可以使用K []中的所有数字都在0和N-1之间的事实,它们是不同的.

对于您的示例案例,您生成一个0到3的随机数r.假设您得到一个随机数.现在,您在数组K []上进行二进制搜索.

Initialize 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[].

   • Initial i = K.length/2 = 1.

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

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

5. 现在我们到达一个空数组.我们现在该做什么？如果我们达到发言权之间的空数组K[j] & K[j+1],然后它只是意味着之间的所有元素K[j],并K[j+1]从阵列丢失K.

6. 因此K[2],数组中缺少上述所有元素,即5和6.我们需要4th element已经丢弃的东西2 elements.因此我们将选择第二个元素6.