Single Number和Single Number II

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?

解析:

a ^ a = 0，a ^ 0 = a

所以对所有的数取异或，其最终结果即为所求。

1     public int singleNumber(int[] A) {
2         int single = 0;
3         for (int i : A) {
4             single ^= i;
5         }
6         return single;
7     }

View Code

2 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?

解析：

(1) a @ a @ a = 0，a @ 0 = a

只要能找到满足上述等式的操作函数@(即自定义进制为3的异或)，即可解决。

(2) a -> one，a @ a -> two，a @ a @ a -> one @ two = 0

即操作一次a，结果记录到one；操作两次，结果记录到two；操作三次时，结果记录到了one和two，则将该结果置为0.

 1     public int singleNumber_3(int[] A) {
 2         int one = 0;
 3         int two = 0;
 4         for (int carry : A) {
 5             while (carry != 0) {
 6                 two ^= one & carry;
 7                 one ^= carry;    
 8                 carry = one & two;
 9             }
10         }
11         return one;
12     }

View Code

3 Single Number II (2)

网上流传的代码如下：

 1     public int singleNumber_3_2(int[] A) {
 2         int one = 0;
 3         int two = 0;
 4         int three = 0;
 5         for (int carry : A) {
 6             two |= one & carry;     // 这两行操作的结果是把carry加到one并进位到two。进位一般是two ^= one & carry ，这里是|，其结果是进位到two后并不继续向高位进位
 7             one ^= carry;           
 8             three = one & two;      // 在这里手动进位到three
 9             one &= ~three;          // one清零
10             two &= ~three;          // two清零
11         }
12         return one;
13     }

View Code

和2是等价的，由于不可能无限循环进位，2是可以写成这样的：

 1     public int singleNumber_3(int[] A) {
 2         int one = 0;
 3         int two = 0;
 4         for (int carry : A) {
 5             two ^= one & carry;
 6             one ^= carry;    
 7             carry = one & two;
 8             two ^= one & carry;
 9             one ^= carry; 
10         }
11         return one;
12     }

View Code

这时候，2和3在看起来就比较像了