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

只要能找到满足上述等式的操作函数@，即可解决。

(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

Single Number和Single Number II