忘我之乘積；及蓄水池抽樣精妙解法
今日面試題：忘我之乘積
給你一個數(shù)組A[1..n]，請你在O(n)的時間里構造一個新的數(shù)組B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法運算。
蓄水池抽樣（Reservoir Sampling)問題分析
問題：
要求從N個元素中隨機的抽取k個元素，其中N無法確定。
這種應用的場景一般是數(shù)據(jù)流的情況下，由于數(shù)據(jù)只能被讀取一次，而且數(shù)據(jù)量很大，并不能全部保存，因此數(shù)據(jù)量N是無法在抽樣開始時確定的；但又要保持隨機性，于是有了這個問題。所以搜索網(wǎng)站有時候會問這樣的問題。
這里的核心問題就是“隨機”，怎么才能是隨機的抽取元素呢？我們設想，買彩票的時候，由于所有彩票的中獎概率都是一樣的，所以我們才是“隨機的”買彩票。那么要使抽取數(shù)據(jù)也隨機，必須使每一個數(shù)據(jù)被抽樣出來的概率都一樣。
分析：
由于N無法確定，數(shù)據(jù)只能讀取一次，并且要求隨機，就是每個元素抽出的概率一樣，都是k/N。
面試的時候，經(jīng)常會在紙上通過一個小的例子來找到好的解決方案。比如先讓你從100個元素中等概率抽取出10個元素。后來又向集合中添加了20個元素，變成了120個元素等概率抽取10個，怎么樣才能隨著N的動態(tài)改變而讓N無論等于多少時這N個元素都等概率被抽取呢？
解法一：最小k個指紋
找到一個哈希函數(shù)能產生隨機數(shù)，同時用一個k個元素的堆用來保存最小的k個元素。那么過一遍所有的元素，計算每個的哈希值，通過堆來選擇k個元素。
這個算法看起來很精妙，會有什么問題嗎？（思考）
解法二：數(shù)學計算
先選中前k個， 從第k+1個元素到最后一個元素為止， 以1/i (i=k+1, k+2,...,N) 的概率選中第i個元素， 并且隨機替換掉一個原先選中的元素， 這樣遍歷一次得到k個元素， 可以保證完全隨機選取。
看來簡單的算法，怎么能確保每個元素被選中的概率是k/N？
任意元素G在i輪留下來的概率：
- P(G留下) = P(G已經(jīng)存在) * P(G沒有被替換)
- = P(G已經(jīng)存在) * (1 - P(G被替換))
- = P(G已經(jīng)存在) * (1 - P(第i個元素要替換某個元素) * P(某個元素是G))
- = (k/i) * (1 - (k/(i+1)) * (1/k))
- = (k/i) * (1 - (1/(i+1)))
- = (k/i) * (i/(i+1))
- = (k/(i+1))
證畢！
這個題有很多的變種，比如，
給你一個長度為N的鏈表。N很大，但你不知道N有多大。你的任務是從這N個元素中隨機取出k個元素。你只能遍歷這個鏈表一次。你的算法必須保證取出的元素恰好有k個，且它們是完全隨機的（出現(xiàn)概率均等）。
從一個不知長度的文件中隨機抽出k行。
從實時的搜索詞中隨機抽出k個詞。
