yeah. 首先要恭喜下自己，昨天的
算法蒙對(duì)了，請(qǐng)看
@陳利人 的
帖子。 【鼓掌】【鼓掌】:)
經(jīng)典面試題：蓄水池抽樣
要求從N個(gè)元素中隨機(jī)的抽取k個(gè)元素，其中N無法確定。
這種應(yīng)用的場(chǎng)景一般是數(shù)據(jù)流的情況下，由于數(shù)據(jù)只能被讀取一次，而且數(shù)據(jù)量很大，并不能全部保存，因此數(shù)據(jù)量N是無法在抽樣開始時(shí)確定的；但又要保持隨機(jī)性，于是有了這個(gè)問題。所以搜索網(wǎng)站有時(shí)候會(huì)問這樣的問題。
這里的核心問題就是“隨機(jī)”，怎么才能是隨機(jī)的抽取元素呢？我們?cè)O(shè)想，買彩票的時(shí)候，由于所有彩票的中獎(jiǎng)概率都是一樣的，所以我們才是“隨機(jī)的”買彩票。那么要使抽取數(shù)據(jù)也隨機(jī)，必須使每一個(gè)數(shù)據(jù)被抽樣出來的概率都一樣。
哎呀媽呀，這題目一天比一天難啊。目測(cè)搞不定啊。
在班車上簡(jiǎn)單分析了下，N的值要到最后才知道，從N個(gè)里面抽k個(gè)元素，要是概率知識(shí)沒有都還給老師的話，每個(gè)元素被抽中的概率是CNk，對(duì)不？唔，既然在N知道之前，就要一樣概率的抽取k個(gè)元素，那我能不能猜想最后的算法其實(shí)是跟N無關(guān)的呢？不管怎么樣先挖個(gè)坑再說，目測(cè)這個(gè)坑不一定能填上。:D