Single Number I

• 題目：有一個數(shù)據(jù)只出現(xiàn)一次，其他數(shù)據(jù)都出現(xiàn)兩次
• 思路：位運(yùn)算（亦或），只要循環(huán)異或，出現(xiàn)兩次的都變成0了，最后只剩下出現(xiàn)一次的single number
• 異或解釋

1. 按位異或運(yùn)算符“^”是雙目運(yùn)算符。
2. 功能是參與運(yùn)算的兩數(shù)各對應(yīng)的二進(jìn)位相異或。
3. 當(dāng)兩個對應(yīng)的二進(jìn)制位相異時，結(jié)果為1
4. 例如9^5 可寫成算式如下:00001001^00000101
5. 結(jié)果為00001100 (十進(jìn)制為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

• 題目：有一個數(shù)據(jù)只出現(xiàn)一次，其他數(shù)據(jù)均出現(xiàn)3次
• 思路：位運(yùn)算

由于只有一個出現(xiàn)一次的數(shù)字，其余數(shù)字都是出現(xiàn)三次
針對于序列中出現(xiàn)三次的所有數(shù)字的每一位來說，相加的結(jié)果只有兩種：1+1+1==3 或者0+0+0=0
所以加上只出現(xiàn)一次的數(shù)字的對應(yīng)位數(shù)字的話，結(jié)果有兩種：0或4
所以對上述的每一位求和之后對3取余，結(jié)果為：1或0
當(dāng)結(jié)果為1的時候，也就是這個位上出現(xiàn)了只出現(xiàn)一次的數(shù)字

• 按位或運(yùn)算

1. 功能是參與運(yùn)算的兩數(shù)各對應(yīng)的二進(jìn)位相或。
2. 只要對應(yīng)的二個二進(jìn)位有一個為1時，結(jié)果位就為1。
3. 例如：9|5可寫算式如下： 00001001|00000101
4. 結(jié)果為：00001101 (十進(jìn)制為13)
   也就是9|5=13

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

Single Number III

• 題目：數(shù)組中只出現(xiàn)一次的兩個數(shù)字
• 思路：

1. 異或思想，一個數(shù)與自己異或?yàn)?，一個數(shù)與0異或?yàn)樽约?/li>
2. 由于其它數(shù)字兩兩相同，所以所有數(shù)異或則得到這兩個不同數(shù)的異或結(jié)果。取這個結(jié)果的第一個1作為標(biāo)志位
3. 這個標(biāo)志的1，必須是：這兩個數(shù)在該位一個為0，一個為1，因?yàn)槭钱惢虿僮?，結(jié)果為1必然在這里兩個數(shù)字一個為0一個為1
4. 這里的結(jié)果必須是會產(chǎn)生的，也就是說肯定存在異或結(jié)果為1，不然這兩個數(shù)字就是相等的
5. 這樣可以將數(shù)組分為兩組，一組在該標(biāo)志位為1，一組在該標(biāo)志位為0，這兩個不同數(shù)字分別在這兩組內(nèi)
6. 將兩組內(nèi)的數(shù)分別異或，得到兩個結(jié)果則為這兩個不同的數(shù)

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;
    }
}