[数据结构与算法]剑指offer04：只出现一次的数字

**题目：**输入一个整数数组，数组中只有一个数字出现了一次，而其他的数字出现了3次，请找出那个只出现一次的数字。例如数组为[0,1,0,1,0,1,100],则只出现一次的数字是100。
分析：
之前有一道类似的题目：输入一个整数数组，数组中只有一个数字出现了一次，而其他的数字出现了2次，请找出那个只出现一次的数字，这个题目的做法只需要异或就能完成，因为任何一个数字异或于它自己的结果都是0，0异或那个只出现一次的数字就等于那个数字，那么数组中所有数字进行异或运算最终结果都是那个只出现一次的数字，但这道题是出现三次相同的数字异或的结果是数字本身，如图，只凭借异或是无法得到那个只出现一次的数字的。

那么应该怎么做呢？
可以看图中下半部分的例子，[0,1,0,1,0,1,4],把它们展示成二进制形式，每一位都对好相加，所有数字中的第i位之和能被3整除说明只出现一次的第i位的数字一定是0，比如最后一位相加为3，能被3整除，所以那个数字最后一位是0，同理，所有数字中的第i为之和不能被3整除，余1，则那个数字第i位为1,最种再将其转换为十进制即可，就找到它的值了。
代码：

package com.wzc;

public class SingleNumber {
    /*
    * 输入一个整数数组，数组中只有一个数字出现一次，而其他数字出现三次，请找出那个只出现一次
    * 的数字，例如如果输入的数组为[0,1,0,1,0,1,100],则只出现一次的数字是100.
    * */
    public static void main(String[] args) {

    }
    public int singleNumber(int[] nums){
//        该数组记录每一位的和
        int[] bitSums = new int[32];
//        每个数字相加
        for(int num:nums) {
            for (int i = 0; i < 32; i++) {
                //        i代表从左起第i个数位
//                累加每个数字的每一位
                bitSums[i] += (num >> (31 - i)) & 1;
            }
        }
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result<<1)+bitSums[i]%3;
//            result = result << 1;
//            result = result + bitSum[i]%3;
        }
        return result;
    }

}

代码解析：传入singleNumber方法参数是所要求的数字，然后通过bitSums数组收集数组每个数字的二进制形式的每一位的和，result最开始设置为0，由于数组第0位保存的最高位的和，向左移一位，最后一位腾出个0，然后最后一位再加上bitSum的和的3取余，如此反复，最终得到想要的结果。