2.5 实例4：随机索引

给定一个可能重复的整数数组，随机输出给定目标编号的索引。可以假设给定的目标编号必须存在于数组中。

思路：利用哈希表把所有相同元素的索引保存下来，然后利用随机函数从中选择一个。

这种题目属于水塘抽样（Reservoir Sampling）类题型，是一组随机抽样算法，而不是某一个具体的算法。这类算法主要用于解决这样一个问题：当样本总体很大或者在数据流上进行采样时，往往无法预知总体的样本实例个数N。那么Reservoir Sampling就是这样一组算法，即使不知道N，也能保证每个样本实例被采样到的概率依然相等。

这个算法是从总体S中抽取前面k个实例放入预置的数组中，这个数组就是最后要返回的抽样结果。对于后面的所有样本实例，从i=k开始，对每一个生成[0，i]的随机数rnd，若rnd<k，则用当前流中的元素替换result[i]。

这样做为什么能保证每个实例被抽到的概率相等而且概率为k/（n+1）呢？

分析如下：对于第i个实例，当算法遇到它时，它被选中进入result的概率是k/（i+1），那么它出现在最后的result的情况是，i后面所有的实例都没有取代它。i后面任何第t（t>i）个实例取代i的概率是k/[（t+1）/k]=1/（t+1），即t被选中的概率是k/（t+1），而且被选中取代原来i所在的位置的概率是k/[（t+1）/k]。所以后面任意一个实例不取代i的概率就是1-1/（t+1），那么所有的情况都发生，最后i才能留在result中，这样就是一个连乘的结果：（k/（i+1））×（1-1/（i+2））×（1-1/（i+3））×…×（1-1/（n+1））=k/（n+1）。