Java O(N) time with O(1) space by bit manipulation


  • 11
    K
    public int singleNumber(int[] nums) {
        int[] digits = new int[32];
        for(int i=0; i<nums.length; i++){
            int mask = 1;
            for(int j=31; j>=0; j--){
                if((mask & nums[i])!=0)
                    digits[j] ++;
                mask <<= 1;
            }
        }
        int res = 0;
        for(int i=0; i<32; i++){
            if(digits[i]%3==1)
                res += 1;
            if(i==31)
                continue;
            res <<= 1;
        }
        return res;
    }

  • 0
    H

    so genius................


  • -1
    This post is deleted!

  • 0
    Y

    The extra memory used is constant, that should be allowed.


  • 0
    X

    I think the last 6 line should be changed to if(digits[i]%3>0). Otherwise, there will be not covered the case that the exceptional number appears in TWICE, such as {1,3,4,1,3,4,5,5,1,3,4}


Log in to reply
 

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