Comparing three solutions


  • 1
    C

    Solution 1:

    Suppose the required return value is ret. Each bit of ret is calculated by the respective bit of A[0:n-1].

        int singleNumber3(int A[], int n) {
        int m=32;
        int ret = 0;
        while(m--)
        {
            ret = ret >> 1;
            ret &= 0x7fffffff;
            int sum = 0;
            for(int i=0;i<n;i++)
            {
                sum += A[i] & 0x00000001;
                A[i] = A[i] >> 1;
            }
            if(sum%3){
                ret |= 0x80000000;
            }
        }
        return ret;
    }
    

    Solution2:
    Solution1 needs 32*n passes of loop. Solution2 is found on the Internet, see http://blog.csdn.net/bigapplestar/article/details/12275381 . However the bit operation is confused. Therefore I write solution3, and try to explain it.

        public int singleNumber(int[] A) {  
        int once = 0;  
        int twice = 0;  
        for (int i = 0; i < A.length; i++) {  
            twice |= once & A[i];  
            once ^= A[i];  
            int not_three = ~(once & twice);  
            once = not_three & once;  
            twice = not_three & twice;  
        }  
        return once;  
    } 
    

    Solution3:

    My solution3 seems more easy-to-understand compared with solution2. Suppose the i-th bit of one, two, thr (one_i, two_i, thr_i) is used to count how many bits in A[0-n-1]_i is 1.
    # one_i two_i thr_i
    1 1 0 0
    2 0 1 0
    3 0 0 0
    4 1 0 0
    5 0 1 0
    6 0 0 0
    ....

    so we have:

    if(A[i] == 1)
    if(one == 0)
    one = 1;
    else
    one = 0;
    if(two == 0)
    two = 1;
    else
    two = 0;
    if(thr == 0)
    thr = 1;
    else
    thr = 0;
    when thr=1
    one=two=0;

    So with the bit operation we have:

        int singleNumber3(int A[], int n) {
        int one=0, two=0, thr=0;
        while(n--)
        {
            //thr ^= (one & two & A[n] );
            two ^= one & A[n];
            one ^= A[n];
            thr = one & two;
            one = (~thr) & one;
            two = (~thr) & two;
            //thr = (~thr) & thr;
        }
    

    Hope this may help.


Log in to reply
 

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