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);}}
