题目描述

题解

位运算

这道题因为相同的数字会出现三次, 而三次异或的结果还是该数字, 所以不能沿用上一道题的方法. 但是依然可以围绕位运算去思考.

对于二进制形式下的每个数字, 在某一位上, 如果是1的话, 那么出现3次的话频数就是3. 如果是0的话, 那么出现3次的频数还是0.共同点就是三个相同的数在某一位上的和取3的余数一定为0. 抓住这点, 将数组中所有数的某一位加起来, 如果结果求3的余数是0, 那么说明只出现一次的数在该位为0, 如果结果求3的余数不为0, 那么说明只出现一次的数在该位一定为1, 根据这个规律就可以求出那个落单的数了

算法思路

首先将二进制形式下的所有数的每一位和求出来, 放在一个32位的数组中

对这个数组逐位取3的余数, 如果为0, 那么该位为0, 如果不为0, 该位为1

将结果输出

public int singleNumber(int[] nums) {
    int res = 0;
    int[] bitSum = new int[32];

    for (int num : nums) {
        int bitMask = 1;
        for (int i = 31; i >= 0; i--) {
            if ((num & bitMask) != 0) {
                bitSum[i]++;
            }
            bitMask = bitMask << 1;
        }
    }

    for (int i = 0; i < 32; i++) {
        res = res<<1;
        res += bitSum[i]%3;
    }

    return res;
}