leetcode 260 single number iii

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:

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?

public class  {
  public static void main(String[] args){
    System.out.println(6&(-6));
  }
  public static int[] singleNumber(int[] nums) {
    
    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;
  }
}

leetcode 260 single number iii

近期文章

近期评论

标签

热门

文章归档

分类目录

功能