算法复习5——找数组中只出现一次的两个数（异或的使用） java

【算法复习5——找数组中只出现一次的两个数（异或的使用）】
文章图片

思路：两个相同的数字异或等于0
- 假设数组中只有一个数字是只出现了一次的，那么从头到尾将数组中所有数字都进行异或，得到的最终结果就是这个数字。
- 题目中的数组是有两个数字只出现一次的，假设为a和b，我们依然从头到尾对所有数字进行异或，那么最终结果就是a和b的异或结果。
- a和b的异或结果中有至少一位为1，把结果中第一位1（从右往左数的）记录位置，设为Index，那就说明a和b在Index对应的位上分别为0和1。
- 根据这一位上的区别，将数组分为两组，分别相与，得到a和b。
代码如下：

public int[] FindNumsAppearOnce(int[] array){ if(array==null) return null; int[] res=new int[]{0,0}; //数组中的两个位置分别记录a和b int number=array[0]; for(int i=1; i>1; //右移位 index++; }for(int i=0; i>index) & 1)==0; //将该位为0的全部相与，得到的是一个只出现一次的数字；该位为1的全部相与，得到另一个 if(isZero) res[0]^=array[i]; else res[1]^=array[i]; } return res; }
小结：
- 当相同的数字出现偶数次时，使用异或^可以对这样的数字进行消除**。
- ?将某个数x右移m位，要写成 x=x>>m；而不能只写成 x>>m；

算法复习5——找数组中只出现一次的两个数（异或的使用）