137. Single Number II

我觉得本题过于Tricky了，虽然是Medium，但是对于Bit Manipulation来说，有些Medium甚至比Hard更加烧脑
我在Discuss中找到了一个还算比较简单的解法，也准备模仿这个，大致思路：

• int 是 32位

• 把这32位分开来看：

  • 对于第n位来说，这个位上的所有数字加在一起为sum
  • 应该等于single number在第n位的数字
  • 所以可以通过这个方法，反向构建Single Number

• 空间复杂度：

• 时间复杂度：，也可以等价为

代码如下：

class Solution {
  public int singleNumber(int[] nums) {
    int singleNum = 0;
    for (int shift = 0; shift < 32; ++shift) {
      int acc = 0;
      for (int num : nums) {
        if (((num >> shift) & 0x01) == 1) {
          acc++;
        }
      }
      singleNum |= ((acc % 3) << shift);
    }
    return singleNum;
  }
}