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