数组之数组中只出现一次的数字

1.本题知识点

   位运算，异或

2. 题目描述

  一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

3. 思路

   这题考察的是异或操作，即对应位上值相同为0，值不同为1。

  ① 异或操作满足交换结合律，比如A ^ B ^ A = B ^ (A ^A) = B ^ 0 = B。所以，数组中数字两两异或，若其中有2个单次出现的数字，最后得到的结果就是这2个单次数字的异或结果，其他出现2次的数字都异或抵消掉了。

  ② 通过①的分析，假设数组中只有一个单次的数字，那么异或后的结果就是这个数，所以，考虑把原数组分开，通过什么分开呢？原数组异或结果位数为1的索引值，区分开2个单次的数，最后分别求2个子数组异或的结果即可。

   举例说明：

   ③ 如何知道是哪个位上不同呢？比如上面是第n =3位不同，现在我们要找到这个n。

   方法：通过【原数组异或结果】【从后往前找到第一个1】的位置即可。

   举例：

   Java版本：

package com.algorithm.array;

/**
 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * 时间复杂度O(n)，空间复杂度O(1)
 * @author wxq
 *
 */
public class NumXOR {
	
	public static void main(String[] args) {

		int [] array = {2,4,3,6,3,2,5,5};
		int[] num1 = new int[array.length];
		int[] num2 = new int[array.length];
		findNumsAppearOnce(array, num1, num2);
		
		System.out.println(num1[0] + "  " + num2[0]);
	}
	
	/**
	 * 
	 * @param array
	 * @param num1 存放返回结果
	 * @param num2
	 */
	static void findNumsAppearOnce(int [] array,int num1[] , int num2[]){
		if(array == null || array.length == 0){
			num1[0] = -1;
			num2[0] = -1;
		}
		//1. 求原数组两两异或结果
		int bitResult = 0;
		for(int i =0 ; i < array.length; i++){
			bitResult ^= array[i];
		}
		
		//2. 找到倒数第一个1的位置
		int index = findFirst1(bitResult);
		
		//3. 根据index位上是不是1切分原数组，并将子数组两两异或。
		for(int i =0 ; i < array.length; i++){
			if(isBit1(array[i],index)){
				num1[0] ^= array[i];
			}
			else{
				num2[0] ^= array[i];
			}
		}
		
		//4. 最终得到单次出现数字num1[0] num2[0]
	}
	/**
	 * 找到原数组异或结果的倒数第一个1的位置
	 * @param bitResult
	 * @return
	 */
	static int findFirst1(int bitResult){
		int index = 0;
		while((bitResult & 1) == 0){
			bitResult >>= 1;
			index++;
		}
		
		return index;
	}
	
	/**
	 * 判断数字第index位置上是不是1
	 * @param target
	 * @param index
	 * @return
	 */
	static boolean isBit1(int target, int index){
		
		return ((target >> index) & 1) == 1;
	}
}