数组中唯一的元素

package JBArray;

import org.omg.CORBA.INTERNAL;

/**
 * 问题描述：数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次，写一个函数， 找出被重复的数字。
 */
public class xor_findDup {
	
	/**
	 * 数字求和法
	 * 算法思路：
	 *          对数据所有项求和
	 *          然后减去1~N-1的和
	 * @param a
	 * @return
	 */
	public static int xor_findDup(int[] a){
		int n = a.length;
		int tmp1=0;
		int tmp2=0;
		for (int i = 0; i < n-1; i++) {
			tmp1 += (i+1);
			tmp2 += a[i];
		}
		tmp2 += a[n-1];
		int result = tmp2-tmp1;
		return result;
	}
	
	/**
	 * 异或法
	 * 算法思路：
	 *    异或特点：相同为0，不同为1 
	 *              X^X=0  X^0=X
	 *    (a[1]~a[N-2])，A,A 组成了数组a[N]
	 *    1、设重复数为A
	 *    2、设1~N-2的异或结果为B
	 *    3、则1~N-1的异或结果为A^B
	 *    4、(a[1]~a[N])的异或结果为A^A^B
	 *    5、运算结果：(A^B)^(A^A^B)=A
	 *      
	 * @param a
	 * @return
	 */
	public static int xor_findDup1(int[] a){
		int n = a.length;
		int i;
		int result = 0;
		for(i=0;i<n;i++){ 
			result ^= a[i]; //(a[1]~a[N])的异或结果为A^A^B
		}
		for (int j = 0; j < n; j++) {
			result ^= i;  //result已经是A^A^B，再与1~N-1的异或结果A^B异或则得到了A
		}
		return result;
		
	}
	
	
	public static void main(String[] args){
		int[] a = {1,2,1,3,4};
		int missingNum = xor_findDup(a);
		System.out.println(missingNum);
	}

}