Given an array of integers, every element appears three times except for one. Find that single one.
这道题的前身是Single Number:
Given an array of integers, every element appears twice except for one. Find that single one.
如果能使用额外的空间的话，用hashmap（unordered_map in C++)能得到很直观的算法。但是这两题都要求Linear time with constant extra space. 对于基本版的Single Number，异或操作能够很好的做到两次出现就抵消
class Solution {
public:
int singleNumber(int A[], int n) {
int m = 0;
for (int i=0; i<n; i++)
m ^= A[i];
return m;
}
};
但是对于出现三次的情况，异或就无用武之地了，我们需要找出一个类似异或的但是三次出现才抵消的操作。基本的位运算和算术运算中都没有直接就能胜任的操作（如果有的话，欢迎指正）。
在Leetcode的讨论区，发现了以下答案：
class Solution {
public:
int singleNumber(int A[], int n) {
int result = 0;
for (int i=0; i<32; i++)
{
int count = 0;
for (int j=0; j<n; j++)
if (A[j] >> i & 1)
count++;
result |= (count % 3) << i;
}
return result;
}
};
顿时领悟过来，按上面说的，异或操作在本题中的作用就是两次出现抵消，即使没有能够三次出现抵消的操作，我们也可以自己创造一个，而逻辑很简单：统计这一位1出现的次数，出现三次就抵消。或者说，将这一位1出现的次数对三取模，则结果只能为0或1，将每一位的结果组合起来，就是最终需要的结果。 这一算法从之前的对整个数字进行异或统计变成了对每一位异或统计，算法复杂度提高了，但是能够有效地得到这一题的结果。值得注意的是，这一算法使用了常数数量的额外空间：result和count，而拓展到其他数据结构的时候，只会在count的空间发生变化，但这一变化仍然是常数级的额外空间。
更进一步的优化代码：
class Solution {
public:
int singleNumber(int A[], int n) {
int ones = 0, twos = 0, threes = 0;
for (int i = 0; i < n; i ++)
{
twos |= ones & A[i];
ones ^= A[i];
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
};
这一算法更进一步，使用ones，twos和threes构成一个简单的有限状态机，其中ones表示出现出现一次或三次的位， twos表示出现至少两次的位，当两者都满足时即为出现三次，将ones和twos的相应位清零。
这一题虽然简单，但是仍然收获不少：
- 位运算很重要
- 简洁的写法想不出时，可以先退一步，将基本的逻辑实现了，然后再从长到短，由繁入简。