今天和某同學(xué)聊到面試題，他提到被某投行打擊很深的一個(gè)reservoir sampling問題。
于是我翻了翻。 大致意思在網(wǎng)上很容易找到。
難是難理解其中的思維點(diǎn)： 怎么發(fā)現(xiàn)的這個(gè)解法。
也就是如何詮釋你的歸納法的出發(fā)點(diǎn)。
目前我的總結(jié)是，對(duì)于這種無(wú)限問題，先設(shè)定一個(gè)基礎(chǔ)的通解。 即在n的時(shí)候成立，再想辦法證明當(dāng)n = n+1的時(shí)候，結(jié)論也成立，或與原結(jié)論存在一定的對(duì)應(yīng)關(guān)系 。
這樣就可以推導(dǎo)出來了。