Skip to content

Latest commit

 

History

History
78 lines (63 loc) · 2.22 KB

260. Single Number III.md

File metadata and controls

78 lines (63 loc) · 2.22 KB

260. Single Number III

leetcode Daily Challenge on July 23th, 2020.

Difficulty : Medium

Related Topics : Bit Manipulation

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

  • The order of the result is not important. So in the above example, [5, 3] is also correct.
  • Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution

  • mine
    • Java

      • Bit Manipulation Runtime: 1 ms, faster than 99.80%, Memory Usage: 39.9 MB, less than 26.67% of Java online submissions.

        //O(n)time  O(1)space
public int[] singleNumber(int[] nums) {
    int t = 0;
    for(int num : nums){
        t ^= num;
    }
    int diff = (~t + 1) & t; // or (-t) & t
    int x = 0, y = 0;
    for(int num : nums){
        if((num & diff) != 0){
            x ^= num;
        }else{
            y ^= num;
        }
    }
    return new int[]{x, y};
}

        we have array [1,2,1,3,2,5].
if we group it like  [2,2,3] and [1,1,5], so we can use xor to get the res [3,5].
how to group this array like it?

we can you xor loop the array to get the num t.
int t = 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 0b0011 ^ 0b0101 = 0b0110
we can use the any bit if value is 1. 
so we can choose 0b0010  or 0b0100.

we choose the lowbit ob0010, we can use t & (-t) or t & (~t + 1) to get it.
int lowbit = t & (-t) = 0b00110 & (0b11001 + 1 ) = 0b00110 & 0b11010 = 0b00010.

then we create a res = new int[2], and loop the array, 
if (num & lowbit) == lowbit, we put res[0] ^= num,
else we put res[0] ^= num,
so we can group the array with [2,2,3] and [1,1,5],
and get the result [3,5]