请教各位大侠如何去除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条件相反，但意思是一样的？
相关阅读
哪里有海美迪Q5四核机器国际版固件？微软的azure已经挂了两小时，还没有恢复怎么在电视上看mobdro有没有unlimited data? (转载)感谢白哥们太实在了送来NOTE 4无法运行Google Play商店xbmc/tvmc中文字幕搞不定的进来1+的售后真是没得比有没有办法改高通lte支持的band？求意见 点评： lenovo yoga 2 8 and 10 inch android tablet 18hours海美迪的盒子实在大卡了安卓5.0怎么快速切换中英文输入看来国内流行的托儿早就打入了mitbbs了17寸的笔记本 便携性怎么样 是否完全不能忍也说我用过的售后服务个人觉得，200到300价位的无锁高性能智能手机会成为一个潮流尼玛亏了当初顶住诱惑没买1+一加手机海外市场再次开启预约做指纹的安卓厂都傻了吧马鬃把这么多好硬件的Hack门都堵上到底想哪样?