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