l**********n
发帖数: 303 | 1 K distinct integers in [0, N], select a random number between 0 and N which
is not in the K list.
多谢 |
g***j
发帖数: 1275 | 2 怎么做？
which
【在 l**********n 的大作中提到】
: K distinct integers in [0, N], select a random number between 0 and N which
: is not in the K list.
: 多谢
|
z*********8
发帖数: 2070 | 3 I think this requires pre-processing to map all K integers to last K
integers in the array which takes O(K) time.
After that, you can simply do Rand%(N-K) to get the number which is not in
the K in constant time |
l**********n
发帖数: 303 | 4 具体怎么做？
假如不能用额外的data structure, 还有其他更好的办法么？
【在 z*********8 的大作中提到】
: I think this requires pre-processing to map all K integers to last K
: integers in the array which takes O(K) time.
: After that, you can simply do Rand%(N-K) to get the number which is not in
: the K in constant time
|
k******4
发帖数: 94 | 5 如果可以改变数组的话。first positive integer 抽样可行不。
K distinct integers in [0, N], select a random number between 0 and N which
is not in th........
【在 l**********n 的大作中提到】
: K distinct integers in [0, N], select a random number between 0 and N which
: is not in the K list.
: 多谢
|
j*********6
发帖数: 407 | 6 没看懂 为什么要 map all K integers to last K integers in the array.
为什么最后只需要Rand%(N-K)? 如何N = 10, K array 是 0-7, K= 8， 那么你最终只
能随机出0 1 2 三个随机数，永远都是在array 的范围内？
不太明白 求解答 多谢啦
【在 z*********8 的大作中提到】
: I think this requires pre-processing to map all K integers to last K
: integers in the array which takes O(K) time.
: After that, you can simply do Rand%(N-K) to get the number which is not in
: the K in constant time
|
z*********8
发帖数: 2070 | 7 不用额外的ds， 那是要rejection sampling吗？
【在 l**********n 的大作中提到】
: 具体怎么做？
: 假如不能用额外的data structure, 还有其他更好的办法么？
|
k******4
发帖数: 94 | 8 1）随机算法，将k个数排序，平均时间klogk，随机选一个数，binary search排序的数
组，如果在其中，继续，否则返回这个数。平均复杂度(k+n/(n-k))logk.
2)将k个数排序，klogk。然后用reservoir sampling。时间是(n+k)logk。
【在 l**********n 的大作中提到】
: 具体怎么做？
: 假如不能用额外的data structure, 还有其他更好的办法么？
|
k******4
发帖数: 94 | 9 第二种方法稍稍改一下可以将时间变成klogk,对于排好序的元素A[i], A[i+1](A[i]+1
< A[i+1]),如果A[i] + (1+rand()%（S+A[i+1]-A[i]-1)在区间【A[i]+1, A[i+1]-1】,
替换当前的sample，否则保留，同时S += A[i+1]-A[i]-1
【在 k******4 的大作中提到】
: 1）随机算法，将k个数排序，平均时间klogk，随机选一个数，binary search排序的数
: 组，如果在其中，继续，否则返回这个数。平均复杂度(k+n/(n-k))logk.
: 2)将k个数排序，klogk。然后用reservoir sampling。时间是(n+k)logk。
|
f*****2
发帖数: 141 | 10 这K个intergers应该是已知的吧？那这样可不可以？
int generate(int *kList, int K, int N)
{
int num;
gen:
num = rand()*N;
for (int i = 0; i < K, i++)
{
if num == kList[i];
goto gen;
}
return num;
}
which
【在 l**********n 的大作中提到】
: K distinct integers in [0, N], select a random number between 0 and N which
: is not in the K list.
: 多谢
|
k******4
发帖数: 94 | 11 这就是随机算法了，稍稍改进，可以二分查找num是否在kList中。
【在 f*****2 的大作中提到】
: 这K个intergers应该是已知的吧？那这样可不可以？
: int generate(int *kList, int K, int N)
: {
: int num;
: gen:
: num = rand()*N;
: for (int i = 0; i < K, i++)
: {
: if num == kList[i];
: goto gen;
|
f*****2
发帖数: 141 | 12 binary search是比遍历要快，但是binary search前得先排序，这个排序消耗的时间能
不能抵消binary search节省的时间？感觉这个复杂度不好分析啊
【在 k******4 的大作中提到】
: 这就是随机算法了，稍稍改进，可以二分查找num是否在kList中。
|
u*****o
发帖数: 1224 | 13 这个题和reservior sampling 是什么关系呢？
假如 N =100， K=10
reservior sampling是说，a[0]-a[9]就是前10个数，从a[10]开始，generate a
random number j in N, if j < k, 替换， 否则skip到下一个数。
这个题的意思是不是说， a[0]- a[9] 还是1-k这些数，从a[10]开始，generate a
random number j in N, if j > k, return the number, else skip to next number.
和reservior sampling条件相反，但意思是一样的？ |
