算法1

(位运算) $O(n^2)$

基于位运算，若一个数字出现三次，那么它的二进制表示中的每一位也出现三次。把数组中的所有出现三次的数字的二进制表示的每一位分别加起来，则每一位的和都能被3整除，再把所求的那个数字的每一位分别加上去，若二进制对应位的和还能被3整除，则所求数字对应位为0，否则为1。最终，得到所求数字的二进制表示。

Java 代码

class Solution {
    public int findNumberAppearingOnce(int[] arr) {
     if(arr==null || arr.length<=0)
            throw new RuntimeException();
        int[] bitSum = new int[32];
        for(int i=0;i<32;i++)
            bitSum[i]=0;
        for(int i=0;i<arr.length;i++) {
            int bitMask=1;
            for(int j=31;j>=0;j--) {
                int bit=arr[i]&bitMask;  //注意arr[i]&bitMask不一定等于1或者0，有可能等于00010000
                if(bit!=0)
                    bitSum[j]+=1;
                bitMask=bitMask<<1;
            }
        }
        int result=0;
        for(int i=0;i<32;i++) {
            result=result<<1;
            result+=(bitSum[i]%3);
            //result=result<<1;  //不能放在后面，否则最前面一位就没了
        }
        return result;
    }
}