c*****o
发帖数: 178 | 1 在glassdoor上看到一道题目：
Given a file of unknown size, devise an algorithm to give equal probability
randomization to choosing a single line given a one line buffer space.
请教思路？ | r**u
发帖数: 1567 | 2 这个刚有人总结过，我copy&paste。
要求从N个元素中随机的抽取1个元素, 其中N无法确定(数据流)。
int Num;
int i = 0;
int choose = 0;
while(scanf("%d", &Num)&& Num != 0){
if (((double)rand()/(double)RANDOM_MAX) < (1.0 / (double)++i))
choose = Num;
}
cout << choose <
总是选择第一行， 二分之一几率选择第二行， 以此类推， K分之一机率选择第K行，
当while 执行完毕，假设N个数字，则每个数字被选择的机率均为1/N
第一行被选择的机率为:
1 * 1/2 * 2/3 * 3/4 *.... (N-1)/N = 1/N
第K行被选择的机率为：
1/K * K/(K+1) * .... (N-1)/N = 1/N
probability
【在 c*****o 的大作中提到】
: 在glassdoor上看到一道题目：
: Given a file of unknown size, devise an algorithm to give equal probability
: randomization to choosing a single line given a one line buffer space.
: 请教思路？
|
|
