一、题目描述

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

• 思路
  在线性时间内从一个数组中找到只出现一次的数（其他数都是出现两次），可以使用抑或运算，相同为0不同为1。
  当出现偶数次的数抑或的结果为0
  而出现奇数次的数抑或的结果为（如果是与0抑或运算）它本身

public class Solution {
    public int singleNumber(int[] A) {
        if(A == null)
            return 0;
        
        int k = 0;
        for(int i=0; i<A.length; i++){
            k = k ^ A[i];
        }
        
        return k;
    }
}

二、题目描述（进阶）

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
第一版回顾

• 思路
  求在不使用额外空间且时间复杂度为O(n)时，只出现一次的数（其他数都出现3次）
  意味着标记等方法都不能用，首先想到的是二进制的位运算，在第一版中利用异或运算将出现2次的数消除，而出现1次的保留了下来，可以借鉴这样的思路。
  首先转化为二进制表示，通过统计所有数每位二进制中1出现的次数，并对3取模，即可把出现3次的数全部消除且保留了出现1次的数，此时对应的二进制即为出现1次数的值。
  例如{1，1，1，2}，变为二进制后对应的每位相加求1出现的个数，求得是1和3（从高位），再对每位统计对3取模，为1和0，此时表示的二进制10即为只出现1次的数2
  以下为上述思路的实现，对于更优的位运算解法还需要学习！

public class Solution {
    public int singleNumber(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        if(A.length == 1) //特殊情况需特判
            return A[0];
        
        int ans = 0;
        for(int i=0; i<32; i++){ //int类型范围是32位二进制
            int bitCnt = 0;
            for(int j=0; j<A.length; j++){
                bitCnt += ((A[j] >> i) & 1); //求每一位二进制对应1的个数
            }
            //将出现3次的数的影响消除
            bitCnt %= 3; 
            //先左移i位到对应位数，再或运算求出当前对应的二进制数（或运算不影响之前统计的二进制表示）
            ans = ans | (bitCnt << i); 
        }
        
        return ans;
    }
}