> 問題：給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給幾個(gè)數(shù)，如何快速判斷這幾個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中?
> 解決：unsigned int
的取值范圍是0到2^32-1。我們可以申請(qǐng)連續(xù)的2^32/8=512M的內(nèi)存，用每一個(gè)bit對(duì)應(yīng)一個(gè)unsigned
int數(shù)字。首先將512M內(nèi)存都初始化為0，然后每處理一個(gè)數(shù)字就將其對(duì)應(yīng)的bit設(shè)置為1。當(dāng)需要查詢時(shí)，直接找到對(duì)應(yīng)bit，看其值是0還是1即可。
posted on 2011-08-30 21:01
jadmin 閱讀(142)
評(píng)論(0) 編輯 收藏