给你n个数，其中有且仅有三个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那三个数（代码）。

public class FindOdd {
	public static void main(String args[]){
		for(int i=0;i<10000;i++){
			if(!test()){
				System.out.println("Error Occurs: "+i);
				break;
			}
		}
		System.out.println("Well Job! All Pass.");
	}
	
	public static boolean test(){
		int num = (int)(Math.random()*102400)*2;
		int multi = 500;
		int[] test = new int[num+3];
		for(int i=0; i<num;i+=2){
			test[i] = (int)(Math.random()*num*multi);
			test[i+1] = test[i];
		}
		test[num] = (int)(Math.random()*num*multi);
		test[num+1] = (int)(Math.random()*num*multi);
		while(test[num+1]==test[num])
			test[num+1] = (int)(Math.random()*num*multi);
		test[num+2] = (int)(Math.random()*num*multi);
		while(test[num+2]==test[num]||test[num+2]==test[num+1])
			test[num+2] = (int)(Math.random()*num*multi);

		System.out.println("test["+num+"]: " + test[num]);
		System.out.println("test["+(num + 1)+"]: " + test[num+1]);
		System.out.println("test["+(num + 2)+"]: " + test[num+2]);
		
		int[] result= findThree(test);
		
		System.out.println("result[0]: " + result[0]);
		System.out.println("result[1]: " + result[1]);
		System.out.println("result[2]: " + result[2]);
		
		return (result[0]==test[num]&&result[1]==test[num+1]&&result[2]==test[num+2])
			||(result[0]==test[num]&&result[2]==test[num+1]&&result[1]==test[num+2])
			||(result[1]==test[num]&&result[0]==test[num+1]&&result[2]==test[num+2])
			||(result[1]==test[num]&&result[2]==test[num+1]&&result[0]==test[num+2])
			||(result[2]==test[num]&&result[0]==test[num+1]&&result[1]==test[num+2])
			||(result[2]==test[num]&&result[1]==test[num+1]&&result[0]==test[num+2]);
	}
	
	public static int[] findThree(int[] list){
		int[] result = new int[3];
		int nums1=0,nums2=0,result1=0,result2=0;
		int exploc = 1;
		int temp;
		while(true){
			nums1=0;
			nums2=0;
			result1=0;
			result2=0;
			
			for(int i=0;i<list.length;i++){
				if((list[i]&exploc)==exploc){
					//the k-th bit is 1
					nums1++;
					result1^=list[i];
				} else{
					//the k-th bit is 0
					nums2++;
					result2^=list[i];
					
				}
			}
			if((nums1&1)==1){
				temp = nums2;
				nums2 = nums1;
				nums1 = temp;
				temp = result2;
				result2 = result1;
				result1 = temp;
			} 
			//nums1 are even
			
			if(result1==0){
				//these three number are in zeros
			}else{
				//there are only one in zeros, so
				result[0] = result2;
				
				int j=0;
				int exp = 1;
				while(true){
					if((result1&exp)==exp)
						break;
					j++;
					exp<<=1;
				}
				
				result1 = 0;
				result2 = 0;
				for(int i=0;i<list.length;i++){
					if((list[i]&exp)==exp){
						//the oneloc-th bit is 1
						result1^=list[i];
					} else{
						//the oneloc-th bit is 0
						result2^=list[i];
					}
				}
				if((result[0]&exp)==exp){
					result[1] = result1^result[0];
					result[2] = result2;
				}else{
					result[1] = result1;
					result[2] = result2^result[0];
				}
				break;
			}
			
			exploc<<=1;
		}
		
		return result;
	}
}

评论

1 楼 lvbolvtian 2012-08-13  

楼主最好贴上思路先