下载掌阅APP，畅读海量书库
立即打开
给定一个可能重复的整数数组，随机输出给定目标编号的索引。可以假设给定的目标编号必须存在于数组中。
思路：利用哈希表把所有相同元素的索引保存下来，然后利用随机函数从中选择一个。
代码清单2-12 随机索引
这种题目属于水塘抽样（Reservoir Sampling）类题型，是一组随机抽样算法，而不是某一个具体的算法。这类算法主要用于解决这样一个问题：当样本总体很大或者在数据流上进行采样时，往往无法预知总体的样本实例个数 N 。那么Reservoir Sampling就是这样一组算法，即使不知道 N ，也能保证每个样本实例被采样到的概率依然相等。
代码清单2-13 从项目流中随机选择 k 个项目
这个算法是从总体 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）。