137. Single Number II

题目描述：给一个整数数组，其中除了一个元素外每个元素都出现三次，找出这个只出现一次的元素。要求时间复杂度O(n)，空间O(1)。

分析：与136题类似的两个思路可以找到此数，但分别不满足时间和空间复杂度要求。还是利用位运算，但都是奇数次，不能用异或了。

代码一：设一个 sizeof(int) 大小的数组 cnt ，cnt[i] 表示在 i 位出现1的个数，若cnt[i]是3的整数倍则忽略，否则取出该位组成答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        int m = sizeof(int) * 8;        //sizeof(int) 是int的字节数，转换为8个比特位
        vector<int> cnt(m, 0);
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j++)
            {
                cnt[j] += (nums[i] >> j) & 1;          //取第 i 个数的第 j 位
                cnt[j] %= 3;
            }
        int ans = 0;
        for (int j = 0; j < m; j ++)
            ans += (cnt[j] << j);         //不为0的所有位所代表的10进制数的和
        
        return ans;
    }
};

代码二：one 、two、three 分别记录到当前处理的元素为止，二进制 1 分别出现 1、2（mod 3后）次的二进制位。当 one 和two中某一位同时为1，就表示该二进制位上1出现了3次，此时清零。最终one就是结果。这是用二进制模拟三进制运算。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        int n = nums.size();
        for (int i = 0; i < n; i ++)
        {
            two |= (one & nums[i]);   //取已经出现过一次1，且当前数该位也为1的位，然后使two的该位置1
            one ^= nums[i];         //记录mod 3 后的1的个数
            three = ~(one & two);         //取one、two同时为1 的位，再取反用于下一步清零
            one &= three;
            two &= three;
        }
        return one;
    }
};