給40億個(gè)不重復(fù)的unsigned int的整數(shù)

1、1.給40億個(gè)不重復(fù)的unsignedint的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中A.申請(qǐng)512M的內(nèi)存一個(gè)bit位代表一個(gè)unsignedint值讀入40億個(gè)數(shù)，設(shè)置相應(yīng)的bit位讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在B.1.unsignedint32位有40億個(gè)的，這是事實(shí)2.確實(shí)是用位圖做的，512M內(nèi)存C.使用位圖法判斷整形數(shù)組是否存在重復(fù)判斷集合中存在重復(fù)是

2、常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時(shí)我們通常希望少進(jìn)行幾次掃描，這時(shí)雙重循環(huán)法就不可取了。位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個(gè)長度為max1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個(gè)元素置1，這樣下次再遇到5想置位時(shí)發(fā)現(xiàn)新數(shù)組的第六個(gè)元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時(shí)置零其后置一的做法類似于位圖的處理方法故稱位

3、圖法。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。D.我的解法，看看還能不能優(yōu)化了。#include#include#defineBITPERINT32每個(gè)int型字節(jié)數(shù)#defineBITPER8每個(gè)型字節(jié)數(shù)#defineN400000000040億個(gè)數(shù)#defineSIZENBITPERINT#defineMASK0x801000000掩碼猶豫40億個(gè)數(shù)會(huì)超出?？臻g，所以在堆上分配動(dòng)態(tài)

4、數(shù)組。typedefstructBitListunsignedbaseintintLengthBitListP_BitList初始化線性順序表，總位數(shù)為intSizeBITPERintInitBitList(BitListif(BL.base==NULL)printf(“nOutofmemomry!n“)exit(0)內(nèi)存初始化為0SetList(blinput)intresult=“給定數(shù)“if(GetList(blresult)==

5、1)printf(“存在“)DestroyBitList(bl)E.unsignedint[12510241024]=0LOOP:讀下一個(gè)數(shù)據(jù)到x中b[x5]=b[x5]&(15]&(1=20億（這相當(dāng)于折半了）；與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找再然后把這個(gè)文件為又分成兩類:1.次最高位為02.次最高位為1并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)=10億（這相當(dāng)于折半了）；與要查找的數(shù)的次最高位比較并接著