leetcode 260 Single Number III
z
 2019-04-09 10:36:27  

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:

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

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class SingleNumberIII {
  public static void main(String[] args){
    System.out.println(6&(-6));
  }
  public static int[] singleNumber(int[] nums) {
    //1. get the xor of a,b
    int xor = 0;
    for (int i: nums){
      xor ^= i;
    }

    //2. find the last different bits of the xor ans,
    //    note that -xor means opposite all bits of xor and then add 1.
    //    xor & -xor preserves the last '1' bit of xor of a and b
    int diff = xor & -xor;

    //3. for every num, put it into the first group when the diff bit is '1' and put it into the second group when is '0'

    int ans[] = {0,0};

    for (int i: nums){
      if ((i & diff) == 0){
        ans[0] ^= i;
      }
      else{
        ans[1] ^= i;
      }
    }
    return ans;
  }
}