描述 Description

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?

Example

Given [1,1,2,3,3,3,2,2,4,1] return 4

[Single Number II]

分析 Analysis

由于所有数字都出现奇数次，所以无法直接使用Single Number I 中的异或操作。

方法1

考虑到计算机使用二进制存储数字，可以建立一个32位的数字，统计每一位1出现的次数，如果一个整数出现了三次，那么三个0或者三个1对3取余都为0，对每个数的对应位都加起来对3取余，剩下的就是 Single Number 。即创建一个长度为sizeof(int)的数组count[sizeof(int)]，count[i]表示在bit i位出现1的次数。如果count[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。

时间复杂度O(n)，空间复杂度O(1)。

方法2

用整数one记录到当前处理的元素为止，二进制1出现“1次”（mod 3 之后的 1）的有哪些二进制位；用整数two记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的有哪些二进制位；用整数 three (其实就是one XOR two)记录到当前计算的变量为止，二进制1出现“3次”的有哪些二进制位。当one和two中的某一位同时为1时表示该二进制位上1出现了3次，此时需要清零。即用二进制模拟三进制运算。最终one记录的是最终结果。

时间复杂度O(n)，空间复杂度O(1)，但是空间实际大小还是比方法1小些，代码也少些，时间可能也快一点点。

代码 Code

方法1

// 方法1，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        const int W = sizeof(int) * 8; // 一个整数的bit数，即整数字长
        int count[W];  // count[i]表示在在i位出现的1的次数
        fill_n(&count[0], W, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < W; j++) {
                count[j] += (nums[i] >> j) & 1;
                count[j] %= 3;
            }
        }
        int result = 0;
        for (int i = 0; i < W; i++) {
            result += (count[i] << i);
        }
        return result;
    }
};

方法2

// 方法2，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for (int i : nums) {
            two |= (one & i);
            one ^= i;
            three = ~(one & two);
            one &= three;
            two &= three;
        }

        return one;
    }
};