[问答题]
大致伪代码如下：
int count = 1;
string query[m+1]; //为了方便理解，从1开始存
while(scanf("%s",&cur_query)!=EOF) {
count++;
if(count <= m) { // 如果输入小于m，直接存。
query[count] = cur_query;
} else { // 剩余的，就随机一个数，并交换。具体为何，在下述证明可见
int M = random(1, count);
if( M < m) {
query[M] = cur_query;
}
}
证明每个query被抽中的概率相等：（假设总请求量为N）
1. 如果N<=m，每个query都被存下来，那么query被抽中保存下来的概率均为1.所以相等
2. N > m. 将query分成前m个和后m个来看（其实也就对应伪码中if/else 两种处理方式）
- 对于第i个数(i < m)，在前m步被选中的概率仍是1.但是从第m+1步，i就有可能被替换掉，被替换掉的概率是 1/count。第m+1步，count = m+1,所以不被替换的概率为m/m+1。接下来的也就是m+1/m+2、m+2/m+3 。 那么读到第N个数时， 显然第i个数被选中的概率 = 每一步都不替换的概率,即 m/m+1 * m+1/m+2 … n-1/n = m/n
- 对于第i个数(i >= m)时。要想被选中的概率为，首先，在它出现的那一次，M取值要<k,这个概率就是m/count. 接下来每一步都不被替换的计算过程跟上面一样。所以此时第i个数被选中的概率 = m/count * count /count+1 。。。n-1/n = m/n
发表于 2015-03-26 22:13:00
回复(1)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
思路：如果用户查询的数量小于m，那么直接就存起来。如果用户查询的数量大于m，假设为m+i，那么在1-----m+i之间随机产生一个数，如果选择的是前面m条查询进行存取，那么概率为m/（m+i），如果选择的是后面i条记录中的查询，那么用这个记录来替换前面m条查询记录的概率为m/（m+i）*（1-1/m）=(m-1)/(m+i)，当查询记录量很大的时候，m/（m+i）== (m-1)/(m+i)，所以每个query被抽中的概率是相等的。