Java solution with easy to understand explanation


  • 0
    P

    2 # appear only once, meaning they are different at some bit(s)
    so first find out which bits they are different at
    we can do so by xoring 0 with the whole list
    this works because other #s in the list appear twice, so xoring twice will cancel out and give us 0 again
    hence we are really just xoring the 2 different # that we want to find
    Now that we have the bits where these 2 # differ at, we can select any one of these set bits
    it is easiest to select either the right most by using (# bit-wise & with the 2's complement of the #): num & -num;or to select the left most signed bit: Integer.highestOneBit(num);
    Now we separate the #s to 2 group, 1 group is set at the selected bit, and the other group is not set at the selected bit
    Recall earlier we were able to find the differing bits of the 2 #s we want by xoring the whole list
    Now that we have separated the 2 target #s in to different groups, performing xoring will give us exactly our targets

    public class Solution {
        public int[] singleNumber(int[] nums) {
            int diffBit = 0;
            for (int num : nums){
                diffBit ^= num;
            }
            diffBit &= -diffBit;
            int[] retVal = {0,0};
            for (int num : nums){
                retVal[0] = ((diffBit & num) == 0) ? retVal[0] : retVal[0]^num;
                retVal[1] = ((diffBit & num) != 0) ? retVal[1] : retVal[1]^num;
            }
            return retVal;
        }
    }
    

    Obviously the solution would not require bit wise operation if we are not trying to achieve O(1) space but still O(n) time

        public int[] singleNumber(int[] nums) {
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; i++){
    	        if (map.containsKey(nums[i]))
    	        	map.remove(nums[i]);
    	        else
    	        	map.put(nums[i], i);
            }
            Integer[] temp = map.keySet().toArray(new Integer[0]);
            int[] retVal = Arrays.stream(temp).mapToInt(Integer::intValue).toArray();
            return retVal;
        }
    

Log in to reply
 

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