《剑指offer第二版》面试题56 题目二：数组中唯一只出现一次

题目描述

• 在一个数组中除一个数字只出现一次之外，其他数字都出现三次。请找出那个只出现一次的数字。

解题思路

1. 假设只出现一次的数字是A.
2. 如果一个数字出现了3次，则将这个数字的二进制表示的每一位都加起来，那么每一位都可以被3整除。
3. 将数组中所有数字的二进制表示的每一位都加起来，如果某一位可以被3整除，那么A的二进制表示中对应的这一位是0，否则是1。

代码

int findNumbersAppersOnce2(int[] arr){
    if (arr == null || arr.length < 1) {
        return -1;
    }
    if (arr.length == 1) {
        return arr[0];
    }

    int[] sumResult = new int[32];
    for (int i = 0; i < arr.length; i++) {
        int flag = 1;
        for (int j = 0; j < 32; j ++) {
            if ((arr[i] & flag) != 0) {
                // 将arr[i]二进制表示的每一位都加起来放到sumResult中
                sumResult[j] = sumResult[j] + 1;
            }
            flag = flag << 1;
        }
    }

    // 计算只出现一次的值
    int result = 0;
    for (int i = 0; i < 32; i++) {
        if (sumResult[i] % 3 != 0) {
            result = result + (sumResult[i] % 3) * (int) Math.pow(2, i);
        }
    }
    return result;
}