s***f
发帖数: 226 | 1 原题是:
Implement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N
probability for each number.
->No more than O(1) memory
->No more than O(N) time
提供的解法是：
public int randomNumber(int N, int[] K) { // K is sorted
int x = uniform(N - K.length); // 1 .. N - K.length
int last = 0 , i;
for (i = 0; i < K.length; i++) {
if (K[i] - last > x)
return x + last;
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid
numbers
last = K[i];
}
return x + K[ K.length-1 ];
}
概率不好，请大家解释下这个算法什么意思，谢谢。 |
c******e
发帖数: 73 | 2 It is filled all empty slot with n - k
for example
k = {0, 2, 5} n = 6
Uniform(30 generate random 0 - 3 and mapped to the empty slot as 1, 3, 4 . |
e********3
发帖数: 18578 | 3 说到底这个算法就是迅速根据Uniform（N-K.length）的结果r，找到第r个不在K内部，
但是小于N的数字，最原始的版本是O（N－K.length)复杂度，就是按照顺序在N－K这个
集合里面找对应的数字，但是这样效率太低。
底下的程序就是每个K内部的元素为跳板迅速向前跳跃找到下一个对应的数字，这句话
是精髓：
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
注意这个－1很关键，没有－1的话x + K[ K.length-1]就会是K里面的数字，有了－1的
话，每遇到K里面的一个数字，x + K[ K.length-1]会加1。
【在 s***f 的大作中提到】
: 原题是:
: Implement below function.
: int getRandom(int N, int K[])
: Constraints:
: ->K is sorted and contains elements in range [0,N)
: ->Output should be a random number between [0,N) excuding elements from K
: ->probability of generated number should be 1/(N-K.length) and not 1/N
: -->int uniform(int N) is given which returns random number [0,N) with 1/N
: probability for each number.
: ->No more than O(1) memory
|
h**6
发帖数: 4160 | 4 用O(N-k.length)的空间建一个对应表，然后每次查表就可以了。 |
l*********8
发帖数: 4642 | 5 现在还是O（N－K.length)复杂度啊。
可以用O(log K.length)来做吧。
【在 e********3 的大作中提到】
: 说到底这个算法就是迅速根据Uniform（N-K.length）的结果r，找到第r个不在K内部，
: 但是小于N的数字，最原始的版本是O（N－K.length)复杂度，就是按照顺序在N－K这个
: 集合里面找对应的数字，但是这样效率太低。
: 底下的程序就是每个K内部的元素为跳板迅速向前跳跃找到下一个对应的数字，这句话
: 是精髓：
: x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
: 注意这个－1很关键，没有－1的话x + K[ K.length-1]就会是K里面的数字，有了－1的
: 话，每遇到K里面的一个数字，x + K[ K.length-1]会加1。
|
h**6
发帖数: 4160 | 6 我提的方法是O(1)啊，只要不限内存，想多快都可以啊。 |
l*********8
发帖数: 4642 | 7 恩，O(N)内存的话，是可以O(1)时间
我前面说的是， 如果限定O(1) extra 存储的话， 可以有O(log K.length) 时间的算
法。
【在 h**6 的大作中提到】
: 我提的方法是O(1)啊，只要不限内存，想多快都可以啊。
|
l*********8
发帖数: 4642 | 8 O(1) space, O(log m) time, where m is the length the K array:
int randomNumber(int N, int *K, int m) {
int x = uniform(N - m);
int low = 0, up = m;
while (low < up) {
int mid = low + (up-low)/2;
if (x <= K[mid] - mid)
up = mid;
else
low = mid + 1;
}
return x + up;
} |
h**6
发帖数: 4160 | |
