9.10擴充性與存儲限制（三）——若隻有4KB記憶體可用，該如何列印數組中所有重複的元素

/**
	 * 思路：4KB最多殉職8*4*2^10個比特。比32000大。建立含有32000個比特的位向量，其中每個比特代表一個整數。
	 * 遇到重複元素，列印出來。
	 * @param array
	 */

	public static void checkDuplicates(int[] array){
		BitSet bs=new BitSet(32000);
		for(int i=0;i<array.length;i++){
			int num=array[i];
			int num0=num-1;//Bitser從0開始，數字從1開始
			
			if(bs.get(num0)){
				System.out.println(num);//列印原值
			}else{
				bs.set(num0);//存入num0
			}
		}
	}
           

class BitSet{
	int[] bitset;
	public BitSet(int size){
		bitset=new int[size>>5];//除以32
	}
	
	public boolean get(int pos){
		int wordNumber=pos>>5;//除以32
		int bitNumber=pos&(0x1F);//除以32取餘數
		return (bitset[wordNumber]&(1<<bitNumber))!=0;
	}
	
	public void set(int pos){
		int wordNumber=pos>>5;//除以32
		int bitNumber=pos&(0x1F);//除以32取餘數
		bitset[wordNumber]|=(1<<bitNumber);
	}
	
}
           

注意：也可參考JAVA内置的BitSet類。