题解 | #数组中只出现一次的两个数字#

内容见注解。主要根据异或的性质，可查询位运算符的用法，异或（^）的部分性质如下：
1. 对于任何数x，都有x^ x=0，x^0=x，同自己求异或为0，同0求异或为自己
2. 自反性 A ^ B ^ B = A ^ 0 = A ，连续和同一个因子做异或运算，最终结果为自己
3. 一个数同自己进行偶数次异或运算结果为0、
4. 一个数同自己进行奇数次异或运算结果为本身。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */

    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        int[]a=new int[2];
        int x=array[0];
        //根据位运算的性质得知，同一数组与自己异或偶数次等于0，0异或任何数等于该数字
        //所以将所有数字一起异或，相同的数字则变成0，最终结果是不同的两个数的异或结果。
        for(int i=1;i<array.length;i++){
            x^=array[i];
        }
        //根据与运算规则，相同为1，相异为0，不断将m左移，直到m和x的某一位相同，记录下来。
        //m所在的位置是所要求的两个数的不同之处（因为x是两数异或得出，所以在这一位异或结果为1）
        int m=1;
        while ((m&x)==0){
            m=m<<1;
        }

        //由上面找出的结果，可以将array中分为两类，一类是在m对应位为1的数，另一类是没有1的数，
        //这样每组只有一个没有配对的数，然后再将每一组所有数放一起异或，结果就是要的数字。
        for(int i:array){
            if((m&i)==0){
                a[0]^=i;
            }else {
                a[1]^=i;
            }
        }
        //从小到大排序，只有两个数字所以只需要交换顺序
        if(a[0]>a[1]){
            a[0]^=a[1];
            a[1]^=a[0];
            a[0]^=a[1];
        }
        return a;

    }

}