P135 只出现一次的两个数字

描述#

这个题目说的是，给你一个整数数组，数组中有两个数字只出现一次，而其他数字都正好出现两次。你要找到这两个只出现一次的数字。

比如说，给你的数组是：
2, 4, 2, 1, 4, 8
在这个数组中，1 和 8 只出现一次，其他的数字都出现了两次。因此你要返回 1 和 8：
1, 8
这里返回两个数字的顺序并不重要，因此你返回 [8, 1] 也是正确的。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int[] singleNumberXOR(int[] nums) {
    int xor = 0, mask = 1;
    for (int num: nums) xor ^= num;
    while ((xor & mask) == 0) mask <<= 1;
    int x = 0, y = 0;
    for (int num: nums) {
      if ((num & mask) == 0) x ^= num;
      else y ^= num;
    }
    return new int[]{x, y};
  }

  // Time: O(n), Space: O(1)
  public int[] singleNumberXOR2(int[] nums) {
    int xor = 0;
    for (int num: nums) xor ^= num;
    int mask = xor & (-xor);
    int x = 0, y = 0;
    for (int num: nums) {
      if ((num & mask) == 0) x ^= num;
      else y ^= num;
    }
    return new int[]{x, y};
  }

}