137. 只出現一次的數字 II

思路

假如現在 $k = 1, m = 3$ ，陣列是 $[1,1,1,3,3,3,5,5,5,4]$。 首先將每個數字都轉成二進制，並記錄每個位置出現的次數。

• $1$：對二進制的$001$來說，它會在位置$0$一共給出$m$次的貢獻。
• $3$：對二進制的$011$來說，它會在位置$0,1$一共給出$m$次的貢獻。
• $5$：對二進制的$101$來說，它會在位置$0,2$一共給出$m$次的貢獻。
• $4$：對二進制的$100$來說，它會在位置$2$一共給出$k$次的貢獻。 若是不考慮出現$k$次的數字$4$，每個位置出現的次數都會是$m$的倍數，因此，只要將各自位置的總和$\%{m}$之後，就能反推出出現$k$次的數字了。

程式碼

位運算

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        const int m = 3;
        int cnt[32]{};
        for(int num : nums) {
            for(int i = 0; i < 32; ++i) {
                cnt[i] += (num >> i) & 1;
            }
        }
        int res = 0;
        for(int i = 0; i < 32; ++i) {
            if(cnt[i] % m != 0) {
                res |= 1 << i;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$