剑指offer 40. 数组中只出现一次的数字

// 题目：输入一个递数组，所有数字都出现了两次出了两个数字之外，输出只出现一次的两个数字

//解法1：类似桶排序，时间O(n)，空间O(n)
public class Main {

	public static void main(String[] args) throws Exception {
		findSum(new int[]{2,4,3,6,3,2,5,5});
	}

	public static void findSum(int[] input) {
		int[] count = new int[999];
		for(int i = 0;i<input.length;i++){
			if(count[input[i]] == 0){
				count[input[i]]++;
			}else{
				count[input[i]]--;
			}
		}
		for(int i = 0;i<count.length;i++){
			if(count[i] == 1){
				System.out.println(i);
			}
		}
	}

}

//解法2：使用抑或的方式进行只出现一次的数字筛选，先找到两个唯一的数字二进制有哪位不同，在根据第一位不同的数字进行挑选
public class Main {

	public static void main(String[] args) throws Exception {
		findSum(new int[]{2,4,3,6,6,9,3,2,5,5});
	}

	public static void findSum(int[] input) {
		int sum = 0;
		int result1 = 0;
		int result2 = 0;
		for(int i = 0;i<input.length;i++){
			sum = sum ^ input[i];
		}
		int firstDiff = findFirstDiff(sum);
		for(int i = 0;i<input.length;i++){
			if(isDiff(input[i], firstDiff)){				//如果属于第一类就与第一类进行抑或
				result1 = result1 ^ input[i];
			}else{											//否则与第二类抑或
				result2 = result2 ^ input[i];
			}
		}
		System.out.println(result1+" "+result2);
	}
	
	public static int findFirstDiff(int sum){				//判断两个唯一的数从右向左第一个不同的二进制位是第几位
		int result = 1;
		while((sum & 1) != 1){ 
			result++;
			sum = sum>>1;
		}
		return result;
	}
	
	public static boolean isDiff(int sum, int index){		//判断一个二进制数第index为是否为1
		while(index != 1){
			sum = sum>>1;
			index--;
		}
		if((sum & 1) == 1){
			return true;
		}else{
			return false;
		}
	}

}