题目：
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?
答案：
思路：
这道题是136. Single Number的一个变种，由此引出了这一类问题的解法。我们可以把这类问题归纳描述为：一个数组中所有的数字都出现了K（的倍数）次，只有一个数字出现了一次，求这个数。思路是我们要记录数字出现的次数，当出现了K次的时候就等价于它出现了0次。这个可以通过数字电路的计数器来实现。
比如说当K=2，我们的要设计的计数器就是有2个状态：0,1。当计数为2时又变回0。这样我们的计数器就需要1个bit去存储所有的状态。然后我们要考虑计数器的状态转换。假设原状态为a，然后新来的bit是b那么我们有：当a=0, b=1 || a=1,b=0的时候新状态为1，也就等价于(~a&b)||(a&~b) = a^b。所以这就是我们要求异或的原因。
同样的，当K=3的时候，我们要设计的计数器就有3个状态：0,1,2。我们就需要2个bit去存储所有的状态。假设我们用a,b表示计数器的两个位，c表示新来个bit，那么计数器的逻辑就是a = a&~b&~c + ~a&b&c；b = ~a&b&~c + ~a&~b&c，这个推导过程留给读者。最后的结果，当计数为0的时候结果是0，当计数不为0的时候结果为1，也就是a|b。
注意上面说的1-bit或者2-bit计数器都只是记录最后结果的一个bit的状态的，由于输入/输出是Integer，所以我们需要32个这样的计数器，也就是用1个或者2两个Integer来表示。
参考代码：
public class Solution {
public int singleNumber(int[] nums) {
int a = 0,b = 0;
for(int i = 0; i < nums.length; i++) {
int temp = (~a&b&nums[i]) | (a&~b&~nums[i]);// a的新状态保存在temp中，因为b的新状态要根据a原来的状态推导出来
b = (~a&~b&nums[i]) | (~a&b&~nums[i]);
a = temp;
}
return a|b;
}
}
参考阅读：
https://discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions
| 
转播
