关于java:算法复习5找数组中只出现一次的两个数异或的使用

28次阅读

共计 764 个字符，预计需要花费 2 分钟才能阅读完成。

思路：两个雷同的数字异或等于 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<array.length;i++){number^=array[i];
        }
        // 找到后果中第一位 1 的地位
        int index=0;
        while((number & 1)==0){// 与 1 相与为 0 阐明末位是 0
            number=number>>1;// 右移位
            index++;
        }

        for(int i=0;i<array.length;i++){
            // 如果 &1=0，阐明第 index 位上为 0
            boolean isZero =((array[i]>>index) & 1)==0;
            // 将该位为 0 的全副相与，失去的是一个只呈现一次的数字；该位为 1 的全副相与，失去另一个
            if(isZero)
                res[0]^=array[i];
            else
                res[1]^=array[i];
        }
        return res;
}