Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
分析：
本题和上一题 Single Number，考察的是位运算。
- 方法1：创建一个长度为sizeof(int)的数组count[sizeof(int)]，count[i]表示在在i位出现的1的次数。如果count[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
- 方法2：用one记录到当前处理的元素为止，二进制1出现“1次”（mod 3 之后的 1）的有哪些二进制位；用two记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的有哪些二进制位。当one和two中的某一位同时为1时表示该二进制位上1出现了3次，此时需要清零。即用二进制模拟三进制运算。最终one记录的是最终结果。
假设现在有一个数字1，那么我们更新one的方法就是‘亦或’这个1，则one就变成了1，而two的更新方法是用上一个状态下的one去‘与’上数字1，然后‘或’上这个结果，这样假如之前one是1，那么此时two也会变成1，这make sense，因为说明是当前位遇到两个1了；反之如果之前one是0，那么现在two也就是0。注意更新的顺序是先更新two，再更新one，不理解的话只要带个只有一个数字1的输入数组看一下就不难理解了。然后我们更新three，如果此时one和two都是1了，那么由于我们先更新的two，再更新的one，two为1，说明此时至少有两个数字1了，而此时one为1，说明了此时已经有了三个数字1，这块要仔细想清楚，因为one是要‘亦或’一个1的，值能为1，说明之前one为0，实际情况是，当第二个1来的时候，two先更新为1，此时one再更新为0，下面three就是0了，那么‘与’上three的相反数1不会改变one和two的值；那么当第三个1来的时候，two还是1，此时one就更新为1了，那么three就更新为1了，此时就要清空one和two了，让它们‘与’上three的相反数0即可，最终结果将会保存在one中，
方法一：
class Solution {
public:
int singleNumber(vector<int>& nums) {
const int W = sizeof(int) * 8; // 一个整数的bit数，即整数字长
int count[W]; // count[i]表示在在i位出现的1的次数
fill_n(&count[0], W, 0);
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < W; j++) {
count[j] += (nums[i] >> j) & 1;
count[j] %= 3;
}
}
int result = 0;
for (int i = 0; i < W; i++) {
result += (count[i] << i);
}
return result;
}
};
时间复杂度o(n),空间复杂度o(1)
方法2：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0, three = 0;
for (int i : nums) {
two |= (one & i);
one ^= i;
three = ~(one & two);
one &= three;
two &= three;
}
return one;
}
};
时间复杂度o(n),空间复杂度o(1)