??用4KB內(nèi)存尋找重復(fù)元素

用4KB內(nèi)存尋找重復(fù)元素

?題目要求：給定一個(gè)數(shù)組，包含從1到N的整數(shù)，N最大為32000，數(shù)組可能還有重復(fù)值，且N的取值不定，若只有4KB的內(nèi)存可用，該如何打印數(shù)組中所有重復(fù)元素。
?分析：本身是一道海量數(shù)據(jù)問題的熱身題，如果去掉“只有4KB”的要求，我們可以先創(chuàng)建一個(gè)大小為N的數(shù)組，然后將這些數(shù)據(jù)放進(jìn)來，但是這里數(shù)組最大為32KB,而題目有4KB的內(nèi)存限制，我們就必須先確定該如何存放這個(gè)數(shù)組。
?如果只有4KB的空間，那么只能尋址842^10個(gè)比特，這個(gè)值比32000要大的，因此我們可以創(chuàng)建32000比特的位向量（比特?cái)?shù)組），其中一個(gè)比特位置就代表一個(gè)整數(shù)。
?利用這個(gè)位向量，就可以遍歷訪問整個(gè)數(shù)組。如果發(fā)現(xiàn)數(shù)組元素是V,那么就將位置為V的設(shè)置為1，碰到重復(fù)元素，就輸出一下。
?下面的代碼僅供參考，你能看懂就行，不用自己會(huì)寫，面試的時(shí)候也不可能讓你構(gòu)造一個(gè)4k的數(shù)組來測(cè)試

public class FindDuplicatesIn32000{public void checkDuplicates(int[]array){BitSet bs new BitSet(32000);for (int i=0;i<array.length;i++){int num array[i];int num = num -1;if (bs.get(num0)){System.out.println(num);}else{bs.set(num0);}}class BitSet{int[] bitset;public BitSet(int size){this.bitset new int[size >> 5];}boolean get(int pos){int wordNumber=(pos >> 5);//除以32int bitNumber=（pos & 0x1F);//取模32return (bitset [wordNumber](1 <bitNumber))!=0;}void set(int pos){int wordNumber=（pos >> 5);//除以32int bitNumber=（pos & 0x1F);//取模32bitset [wordNumber]=1 <bitNumber;}}
}