LeetCode 只出现一次的数字II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

方法一：利用map将值出现的次数标记，然后找出出现一次的元素。（时间复杂度O(n), 空间复杂度O(n)）

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		map<int, int> myMap;
		//遍历数组，将值与出现的次数标记
		for (auto num : nums) {
			++myMap[num];
		}
		//遍历map，寻找出现一次的元素
		for (auto it : myMap) {
			if (it.second == 1) {
				return it.first;
			}
		}
        return 0;
	}
};

方法二：将int数分为32位，那么按该题的要求，这32位的每一位，所出现过的数目必定是3N或3N+1，3N+1的位级必然是那唯一的一个元素贡献的。对int数res的每个位进行数组位与遍历，出现3N+1的即保留下来，最终刷完32位之后，可得结果。（时间复杂度O(n), 空间复杂度O(1)）

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int count, result = 0, bitN;
		for (int i = 0; i < 32; ++i) {
			count = 0;
			bitN = 1 << i;//右移i位
			for (auto num : nums) {//统计第i位为1的数目
				if (bitN & num) {
					++count;
				}
			}
			if (count % 3 == 1) {
				result |= bitN;
			}
		}
		return result;
	}
};

方法三：使用数字逻辑的计数电路原理，进行标记。参考https://blog.****.net/jiangxiewei/article/details/82227451
我们要运用逻辑门的想法设计一个计数器.计数到3就回归0.对于每一个二进制位,出现了多少次1我们可以用两个二进制表示(因为这题只需要记录%3),00表示出现0次,01表示出现1此,10表示出现2次.这样就记录了三个状态,(题目中是出现三次,其实对于x次,我们也可以同理描述).如下（a为高位,b为低位.两个一起表示一个两位二进制表示的数字）

上面是我们计数器需要达成的目标,一个计数循环.学过数字电路的同学看到这里应该就知道怎么做了.
我们再进一步. 我们遍历数据,每来一个数据c(这里一个二进制)我们的a与b就要开始为c计数,那么有以下情况

上面比较容易明白,来的是0,那么我们不统计,原来a,b的统计结果不变

这里也比较容易明白,当来的是1,那么只要为其计数增加1就好.
接下来就是我们的重头戏了.开始设计逻辑门能让我们的计数器保持3个状态记录循环.
我们观察结果a,可以看到会使结果a=1的状态仅有 ( a为1 && b为0 && c为0 ) || (a为0 && b为1 && c为1),同理可以推出b的表达式.
故可得出公式结果a结果b的表达式:

结果a = (a & ~b & ~c) + (~a & b & c)
结果b = (~a & ~b & c) + (~a & b & ~c)
另外根据分配率公式也可以变成:
结果b = ~a & (~b & c + b & ~c) = ~a & (b^c) //二进制进位逻辑 
再然后根据上图a,c,结果b 三者的关系写出结果a的逻辑 
结果a = a & ~c & (~结果b) + ~a & c & (~结果b) = (~结果b) & (a^c)

（时间复杂度O(n), 空间复杂度O(1)）

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int a = 0, b = 0;
		for (auto x : nums) {
			a = (a ^ x) & ~b;
			b = (b ^ x) & ~a;
		}
		return a;
	}
};