一个文件含有n个元素,只能遍历一遍要求等概率取出其中之一。

解答:

     抽签,5个人抽取5根签,只有一个签为中签。每个人概率为1/5. 

将这n个元素依次遍历,每次得到的数(第L个)取随机数r,r%L==0(0-L之内)

var pickOne(file){

  int lenth = 1;

  while(lenth <= file.size){

    if(random()%lenth == 0){

      pick = file[lenth];

    }

    lenth++;

  }

return pick;

}

1,2,3,4,5,6,7

第一个数:pick = 1 概率100%;

第二个数:pick被替换为第二个数的概率为1/2,前面的数选到概率为1/2

第三个数:pick被替换为第三个数的概率为1/3,前面的数选到概率为1/2*(1-1/3)

第四个数:pick被替换为第四个数的概率为1/4,之前概率为1/3*(1-1/4)

第n个数:pick被替换为第n个数的概率为1/n

原文地址:https://www.cnblogs.com/pandans/p/5002031.html