LeetCode 137. Single Number II

Given an 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?

解析：
给定一组整数，除了一个数值出现1次之外，其他的所有数值都出现了3词次，找到出现了1次的这个数值。这道题目是Single Number的升级版本，没法再按照前一个题目进行异或操作了。但是也是采用位运算解决。
方法1
我们可以建立一个32位的数字，来统计每一位上1出现的个数，如果某一位上为1的话，那么如果该整数出现了3的整数倍次，对3取余结果为0，我们把每个数的对应位都加起来对3取余，最终剩下来的那个数就是单独的数字。
[cc lang=”C++”]
class Solution {
public:
int singleNumber(vector& nums) {
int res = 0;
for (int i = 0; i < 32; ++i) {//循环处理32位数值的每一位 int sum = 0; for (int j = 0; j < nums.size(); ++j) {//遍历每一个数值 sum += (nums[j] >> i) & 1;//当前数字第i位上的数值求和
}
res |= (sum % 3) << i;//对3取余操作，并左移到对应位上 } return res; } }; [/cc] 方法2
同样也是采用位运算的方式，我们构造一个三进制运算表示，当某一位出现3次1时置为0，当出现3n+1次时置为1。取三个整型值one, two, three，均初始化为0，分别用于记录某一位出现1的次数。
具体代码如下
[cc lang=”C++”]
class Solution {
public:
int singleNumber(vector& nums) {
int one = 0, two = 0, three = 0;
for (int i = 0; i < nums.size(); ++i) { two |= one & nums[i];//当新来的为0时，two = two | 0，two不变，当新来的为1时，（当one此时为0，则two = two|0，two不变；当one此时为1时，则two = two | 1，two变为1 one ^= nums[i];//新来的为0，one不变，新来为1时，one是0、1交替改变 three = one & two;//当one和two为1是，three为1（此时代表要把one和two清零了） one &= ~three;//把one清0 two &= ~three;//把two清0 } return one; } }; [/cc] 我们以1,2,1,1为例，而至今分别为： 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 以低位上的1 0 1 1 为例说明。初始one,two,three均为0. 输入为1时，two |= one & nums[i]执行后two为0，one ^= nums[i]执行后one为1，此时three为0； 输入为0时，two为0，one仍然为1，three为0； 输入为1时，two |= one & nums[i]执行后two为1，one为0，three仍然为0，模拟实现了进位操作； 输入为1时，two |= one & nums[i]执行后two为1，one为1，three此时为1，执行 one &= ~three后把one清零，同时也把three也清零了。 后续依次处理，最终剩下的出现一次的One就是所求数值。 参考： http://www.cnblogs.com/grandyang/p/4263927.html http://www.jianshu.com/p/758e799614b2