2.5 實例4：隨機索引

給定一個可能重復的整數數組，隨機輸出給定目標編號的索引。可以假設給定的目標編號必須存在于數組中。

思路：利用哈希表把所有相同元素的索引保存下來，然后利用隨機函數從中選擇一個。

代碼清單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）。