池塘抽样法（水塘抽样）-均等概率随机算法

关联题目 链表随机节点
一般语言提供了随机函数可以实现数的均等概率取，但是要考虑到本题目的链表无法直接标记，如果想直接使用下标,必然要花费空间存入数组。类推，如果是一个很大的文本流，无法在内存打开，那该如何是好？
于是，我们引入池塘抽样法（又称水塘抽样）

池塘抽样法

从S中抽取首k项放入「水塘」中
对于每一个S[j]项（j ≥ k）：
随机产生一个范围从0到j的整数r
若 r < k 则把水塘中的第r项换成S[j]项

用枚举数组S{1，2，3}来帮助理解：

1. 当遍历到S[1]时，概率为1，只有一个数那肯定不存在均等的概念
2. S[2]时，有两个数，那么使用随机函数(这里假定是rand，根据自己语言确定),rand(1)[表示在0-1随机取]，如果取到0则保留当前值S[2]，概率是1/2（rand（0））概率。如果取不到则保留原答案，由1.可知之前值只有S[1]，且概率为1，则此时取S[1]的概率为1 X 1/2。这是的S[1],S[2]的概率均等，都为1/2
3. S[3]时，有三个数，使用函数rand(2),取0时保留S[3]，概率为1/3。否则保持原答案，由2. 可得，S[1],S[2]原保留概率均为1/2，此时如果S[3]未选，则S[1],S[2]保留概率为1/2 X 2/3 = 1/3 ，此时三个数的取值概率均为1/3，遍历结束，得到随机值

代码：

for i, num := range S {//遍历S
    if rand.Intn(i + 1) == 0 {//随机数（当前是第几个数就是随机几个数）等于0
        ans = i//保留答案
    }  
}

【文章转自阿里云代理商 http://www.558idc.com/aliyun.html 欢迎留下您的宝贵建议】