数组中只出现一次的数字

题目1-LeetCode136

先来看一道LeetCode的相似题目，给定一个数组，数组中只有一个数字出现了一次，其余数字都出现了两次，找出出现一次的数字，返回结果。

提示

算法不能使用额外的空间，且时间复杂度是O(1)。

解法

采用异或运算符，^ 相同位为0，不同位是1.所以两个相同的数字进行异或操作，返回结果是0，因此这道题就很容易得出答案了。

代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        // 因为只有一个数字出现了一次，其余数字出现了两次，所以遍历数组所有元素进行异或，异或的结果就是出现了一次的数字。
        for(int i=0;i<nums.length;i++){
            res ^= nums[i];
        }
        return res;
    }
}

牛客剑指Offer

题目

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

分析

这道题与上一道题不同之处在于有两个数字出现了一次，其余数字出现了两次，也可以采用异或操作，我们设最后的两个结果一个是a一个是b，异或到最后是n=a^b。
那怎样才能把它分开呢？
我们可以找出n他的二进制中从右往左数第一次出现1的位，然后根据数组元素的这一位是不是也是1，将数组一分为二，变成两个子数组；因为相同的数字肯定分到同一个子数组中，不同的肯定不在同一个子数组中，所以，a和b不在一个子数组中。最终将两个子数组异或，得到的结果就是a和b。

代码

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int n= 0 ;
        for(int i=0;i<array.length;i++){
            n^=array[i];
        }
        // 计算出res二进制中从右往左数第一个1
        int last = n-(n&(n-1));
        for(int j=0;j<array.length;j++){
            // 第一个子数组的第last位都不是1，两个不同的数肯定不会在同一个子数组中
            if((last&array[j])==0){
                num1[0]^=array[j];
            }else{
                //第二个子数组的last位都是1
                num2[0]^=array[j];
            }
        }
    }
}

需要注意的是上面有个计算出n的二进制中从右往左第一次出现1的位置的公式last= n-(n&n-1);比如n=11100,n-1=11011;n&n-1=11000;n-(n&n-1)=100。