Clear Java solution with explanation


  • 2
    K
    public class Solution {
        public int singleNumber(int[] nums) {
            int one = 0; int two = 0; int three = 0;
            for(int i = 0; i < nums.length; i++){
                // if now one is nums[i], by ANDing and ORing, two now equals to nums[i]
                two |= one & nums[i];
                // if now one is zero, it stores the nums[i] in it
                // if now one is nums[i], it clears the content since a^a = 0
                // if now one is other number, it just accumulates
                one ^= nums[i]; 
                // if now one and two has the same value, it means the 
                // number shows 3 times, thus
                three = one & two;
                // if three is the number, clear this number from the one and two
                // a &= ~b => a - b
                // 0100 | 0011 = 3+4 = 7  (0111)
                // 7 &= ~3 => 0111 & 1100 = 0100 = 4 (7 - 3)
                one &= ~three;
                two &= ~three;
            }
            return one;
        }
    }
    
    // the below code does not meet the complexity requirement, just for fun
    
    public class Solution {
        public int singleNumber(int[] nums) {
            int len = nums.length;
            Arrays.sort(nums);
            int i;
            for(i = 0; i < len - 1 && nums[i] == nums[i + 1]; i += 3);
            return nums[i];
        }
    }

  • 0
    A

    Your solution uses : Arrays.sort(nums);
    Which internally uses 2 pivot Quick Sort, with amortized complexity of O(n.logn)


  • 0
    Z

    7 &= ~3 => 0111 & 1100 = 0100 = 4 (7 - 3)
    I am sorry, but I think this is coincident. For example, 5 - 2 = 3 5 = 0101, 2 = 0010, 3 = 0011 and ~2 = 1101. So 0101 & 1101 = 0101 = 5, not 3.


Log in to reply
 

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