请教各位大侠如何去除reimage repair病毒# PDA - 掌中宝
l*n
1 楼
K distinct integers in [0, N], select a random number between 0 and N which
is not in the K list.
多谢
is not in the K list.
多谢
f*x
2 楼
前几天下载KMPLAYER的副产品，太TMD烦人。
g*j
3 楼
怎么做？
which
【在 l**********n 的大作中提到】
: K distinct integers in [0, N], select a random number between 0 and N which
: is not in the K list.
: 多谢
which
【在 l**********n 的大作中提到】
: K distinct integers in [0, N], select a random number between 0 and N which
: is not in the K list.
: 多谢
f*x
4 楼
up
z*8
5 楼
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
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
6 楼
具体怎么做？
假如不能用额外的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
假如不能用额外的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
7 楼
如果可以改变数组的话。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.
: 多谢
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
8 楼
没看懂 为什么要 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
为什么最后只需要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
9 楼
不用额外的ds， 那是要rejection sampling吗？
【在 l**********n 的大作中提到】
: 具体怎么做？
: 假如不能用额外的data structure, 还有其他更好的办法么？
【在 l**********n 的大作中提到】
: 具体怎么做？
: 假如不能用额外的data structure, 还有其他更好的办法么？
k*4
10 楼
1）随机算法，将k个数排序，平均时间klogk，随机选一个数，binary search排序的数
组，如果在其中，继续，否则返回这个数。平均复杂度(k+n/(n-k))logk.
2)将k个数排序，klogk。然后用reservoir sampling。时间是(n+k)logk。
【在 l**********n 的大作中提到】
: 具体怎么做？
: 假如不能用额外的data structure, 还有其他更好的办法么？
组，如果在其中，继续，否则返回这个数。平均复杂度(k+n/(n-k))logk.
2)将k个数排序，klogk。然后用reservoir sampling。时间是(n+k)logk。
【在 l**********n 的大作中提到】
: 具体怎么做？
: 假如不能用额外的data structure, 还有其他更好的办法么？
k*4
11 楼
第二种方法稍稍改一下可以将时间变成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。
< 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
12 楼
这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.
: 多谢
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
13 楼
这就是随机算法了，稍稍改进，可以二分查找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 的大作中提到】
: 这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
14 楼
binary search是比遍历要快，但是binary search前得先排序，这个排序消耗的时间能
不能抵消binary search节省的时间？感觉这个复杂度不好分析啊
【在 k******4 的大作中提到】
: 这就是随机算法了，稍稍改进，可以二分查找num是否在kList中。
不能抵消binary search节省的时间？感觉这个复杂度不好分析啊
【在 k******4 的大作中提到】
: 这就是随机算法了，稍稍改进，可以二分查找num是否在kList中。
u*o
15 楼
这个题和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条件相反，但意思是一样的？
假如 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条件相反，但意思是一样的？
相关阅读
nook color换用户指南（机主更换）各位回见Costco的Xoom WiFiat&t不让android手机安装第三方程序？vzw的unlimited plan入了个gtablet[好图]《今天和一女孩喝星巴克去了》（共2张照片） (转载)iPhone 4 JB后原来的App还在吗?android怎么在线播放局域网上的音乐/视频？请推荐可以随意添加字典的工具 (转载)t-mobile 的 3g/4g 和 att 的网路不兼容是咋回子事儿来着？Nook Color Andorid 2.2 update Mid-Aprilipad的界面的图标如何缩紧距离请问Galaxy S 4G和Galaxy S i9000一样吗？可以用i9000的ROM来刷机吗？大家推荐一个无DATA可以用GPS的手机NC 里哪个app 看word doc比较好？gtablet Gingerbread vido不要笑我土，请问分析称谷歌可能跳过3.0，直接开源Android 3.1现在最便宜的unlimited data plan是什么？