題目描述：給一個(gè)整數(shù)數(shù)組，其中除了一個(gè)元素外每個(gè)元素都出現(xiàn)三次，找出這個(gè)只出現(xiàn)一次的元素。要求時(shí)間復(fù)雜度O(n)，空間O(1)。

分析：與136題類似的兩個(gè)思路可以找到此數(shù)，但分別不滿足時(shí)間和空間復(fù)雜度要求。還是利用位運(yùn)算，但都是奇數(shù)次，不能用異或了。

代碼一：設(shè)一個(gè) sizeof(int) 大小的數(shù)組 cnt ，cnt[i] 表示在 i 位出現(xiàn)1的個(gè)數(shù)，若cnt[i]是3的整數(shù)倍則忽略，否則取出該位組成答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        int m = sizeof(int) * 8;        //sizeof(int) 是int的字節(jié)數(shù)，轉(zhuǎn)換為8個(gè)比特位
        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 個(gè)數(shù)的第 j 位
                cnt[j] %= 3;
            }
        int ans = 0;
        for (int j = 0; j < m; j ++)
            ans += (cnt[j] << j);         //不為0的所有位所代表的10進(jìn)制數(shù)的和
        
        return ans;
    }
};

代碼二：one 、two、three 分別記錄到當(dāng)前處理的元素為止，二進(jìn)制 1 分別出現(xiàn) 1、2（mod 3后）次的二進(jìn)制位。當(dāng) one 和two中某一位同時(shí)為1，就表示該二進(jìn)制位上1出現(xiàn)了3次，此時(shí)清零。最終one就是結(jié)果。這是用二進(jìn)制模擬三進(jìn)制運(yùn)算。

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]);   //取已經(jīng)出現(xiàn)過(guò)一次1，且當(dāng)前數(shù)該位也為1的位，然后使two的該位置1
            one ^= nums[i];         //記錄mod 3 后的1的個(gè)數(shù)
            three = ~(one & two);         //取one、two同時(shí)為1 的位，再取反用于下一步清零
            one &= three;
            two &= three;
        }
        return one;
    }
};