0和1的把戏

要分享的两个算法题都是用关于位的知识求解的，先透露一下。首先来看第 1 道题：

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目给定一个整数数组，数组中除了一个整数外，其他都是成对出现的，要求得到那个特别的数。初看起来题目非常简单，排个序就好了，然后遍历一遍，这是大部分人最直观的想法，包括我，但是排序的最好复杂度为nlogn，再加上O(n)的遍历时间，结果一定为非线性时间。题目希望能够linear runtime时间内完成，那么仅有一次遍历的机会。所以一定要在这次遍历的时候做一下文章。

题解: 遍历数组，直接异或！相同为 0，相异为 1。举个例子，3，4，3。这三个数异或，可以先将 3 和 3 异或，相同的数异或之后，结果为 0，然后再与 4 异或，0 与任何数异或结果不变。得到的结果为 4. 代码如下（java）：


public int singleNumber(int[] A) {
  int result = A[0];
  for (int i = 1; i < A.length; i++) {
    result = result ^ A[i];
  }
  return result;
}

接下来看第二道题：

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

和第一道题大同小异，只不过是相同的个数由 2 变为 3 了。思路肯定还是在一次遍历的时候完成所有工作，但是这次不能简单的异或了，因为三次的话直接以后又出问题了。

题解： 回过头来再看看第一道题，其实，在异或的时候，我们做的工作是，遇到第一个 3，记住这个 3 遇到一次，记为 1，当再次遇到 3 得时候，将再记录一次 3 遇到了两次，于是我们将 1 改为 0. 注意，这里，我们使用了一个 bit 来表示 2 种状态。对于第二题来说，我们也可以使用这样的思路，不过这里有三个状态，所以我们至少使用 2 个 bit 来表示，到第一次遇到时候，记作 10，当第二次遇到时，记作 01，当第三次遇到时，记作 00。状态变化为00->10->01->00(0->1->2->3)。代码如下（C++）：


int singleNumber(int A[], int n) {
  int ones = 0;
  int twos = 0;
  for (int i = 0; i < n; i++) {
    ones = (ones ^ A[i]) & (~twos);
    twos = (twos ^ A[i]) & (~ones);
  }
  return ones;
}