260. Single Number III

本题又是最可怕的Bit Manipulation，这种题属于，看答案觉得像Medium，但是如果第一次见，比起普通的Hard都难，虽然不是很重要，但是还是做一下把。

1. 遍历，xor每个元素，最后的结果应该是我们要找的两个元素的xor
2. 【难点】这两个元素一定是不同的，所以我们需要找到一个bit来区分这俩
   1. 我们选择的是rightmost 1 bit，具体方法是 num & ~(num-1)
      1. num - 1会把
         1. rightmost 1 bit左边的元素（原来是0）全变成1
         2. rightmost 1 bit 本身变成 0
         3. rightmost 1 bit右边不变
      2. ~(num - 1)会将上面的东西取反
         1. rightmost 1 bit 本身变成 0
         2. rightmost 1 bit左边的元素（原来是1）全变成0
         3. rightmost 1 bit右边全都跟之前不一样
      3. num & ~(num - 1)会
         1. rightmost 1 bit 左边右边都变成0
         2. rightmost 1 bit 只有自己是1
   2. 于是我们可以把这些数分成两组
      1. 一组是rightmost 1 bit是1的，
      2. 一组是rightmost 1 bit是0的
      3. 我们要找的两个数分别在这两个组中，别的重复元素都是结对在同一个组

• 时间复杂度：
• 空间复杂度:

class Solution {
  public int[] singleNumber(int[] nums) {
    int xorResult = 0;
    for (int num : nums) {
      xorResult ^= num;
    }
    // find the rightmost bit
    int set = xorResult & ~(xorResult - 1);
    int result[] = {0, 0};
    for (int num : nums) {
      if ((set & num) != 0) {
        result[1] ^= num;
      }
      else {
        result[0] ^= num;
      }
    }
    return result;
  }
}