single-number-ii

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

题解

利用位运算和有限状态自动机。对32位每位分开看待，按位加，出现三次的对应位加起来一定是3的倍数，所以模3就三种情况：00, 01,10. 模3之后每一位剩下的就是只出现了一次的那个数。余数有两位，记为two, one。int共32位，用两个数twos, ones存放，使用位运算。主要就是用有限自动机，找出如何计算twos和ones了。最后的结果每一位只会是01或00，因此ones的值就是要找的数字。

int singleNumber(vector<int>& nums) {
	int ones = 0, twos = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		ones = ones ^ nums[i] & ~twos;
		twos = twos ^ nums[i] & ~ones;
	}
	return ones;
}