An easy-understood method, can be used in general condtions.


  • 3
    A
    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            if (nums.size()<3) return nums[0];
            int cnt[3]={~0,0,0};
            int cntTemp[3];
            for (int n:nums) {
                cntTemp[0]=(cnt[0]&(~n))|(cnt[2]&n); //3m+0 = (3m+0)+0 or (3m+2)+1
                cntTemp[1]=(cnt[1]&(~n))|(cnt[0]&n); //3m+1 = (3m+1)+0 or (3m+0)+1
                cntTemp[2]=(cnt[2]&(~n))|(cnt[1]&n); //3m+2 = (3m+2)+0 or (3m+1)+1
                swap(cnt,cntTemp);
            }
            return cnt[1]; //bits that have (3m+1) 1bits
        }
    };
    

    The solution can be generalized.
    Suppose given "every element appears k times except for one", we just need an array cnt[k], where every cnt[i] shows the bits on which (mk+i) 1 bits have been found (m∈N).
    Besides, the single number may appear once, twice, ...(k-1) times, using "return ~cnt[0]" can well solve this.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.