Single Number I

• 题目：有一个数据只出现一次，其他数据都出现两次
• 思路：位运算（亦或），只要循环异或，出现两次的都变成0了，最后只剩下出现一次的single number
• 异或解释

1. 按位异或运算符“^”是双目运算符。
2. 功能是参与运算的两数各对应的二进位相异或。
3. 当两个对应的二进制位相异时，结果为1
4. 例如9^5 可写成算式如下:00001001^00000101
5. 结果为00001100 (十进制为12)

public class Solution {
    public int singleNumber(int[] nums) {
        int result=0;
        for(int i=0;i<nums.length;i++){
            result^=nums[i];
        }
        return result;
    }
}

Single Number II

• 题目：有一个数据只出现一次，其他数据均出现3次
• 思路：位运算

由于只有一个出现一次的数字，其余数字都是出现三次
针对于序列中出现三次的所有数字的每一位来说，相加的结果只有两种：1+1+1==3 或者0+0+0=0
所以加上只出现一次的数字的对应位数字的话，结果有两种：0或4
所以对上述的每一位求和之后对3取余，结果为：1或0
当结果为1的时候，也就是这个位上出现了只出现一次的数字

• 按位或运算

1. 功能是参与运算的两数各对应的二进位相或。
2. 只要对应的二个二进位有一个为1时，结果位就为1。
3. 例如：9|5可写算式如下： 00001001|00000101
4. 结果为：00001101 (十进制为13)
   也就是9|5=13

public class Solution {
    public int singleNumber(int[] nums) {
        if(nums == null||nums.length == 0){
            return -1;
        }
        //得到出现一次的数字的值
        int result=0;
        //int为4字节，那么共有32位
        for(int i=0;i<32;i++){
            //保存每一位求和值
            int sum=0;
            for(int j=0;j<nums.length;j++){
                //累加所有数字上第i位的数字
                sum+=(nums[j]>>i)&1;
                //System.out.println("sum"+sum);
            }
            //取余得到第i位上的数字，更新result
            result|=(sum%3)<<i;
            //System.out.println("res+"+result);
        }
        return result;
    }
}

Single Number III

• 题目：数组中只出现一次的两个数字
• 思路：

1. 异或思想，一个数与自己异或为0，一个数与0异或为自己
2. 由于其它数字两两相同，所以所有数异或则得到这两个不同数的异或结果。取这个结果的第一个1作为标志位
3. 这个标志的1，必须是：这两个数在该位一个为0，一个为1，因为是异或操作，结果为1必然在这里两个数字一个为0一个为1
4. 这里的结果必须是会产生的，也就是说肯定存在异或结果为1，不然这两个数字就是相等的
5. 这样可以将数组分为两组，一组在该标志位为1，一组在该标志位为0，这两个不同数字分别在这两组内
6. 将两组内的数分别异或，得到两个结果则为这两个不同的数

public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res=new int[2];
        if(nums == null||nums.length == 0){
            res[0]=0;
            res[1]=0;
            return res;
        }
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum^=nums[i];
        }
        int count=0;
        while ((sum&1)==0){
            sum>>=1;
            count++;
        }
        res[0]=0;
        res[1]=0;
        for(int i=0;i<nums.length;i++){
            if((nums[i]&(1<<count))==0){
                res[0]^=nums[i];
            }else{
                res[1]^=nums[i];
            }
        }
        return res;
    }
}