137. 只出现一次的数字 II

题目描述：

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

说明：

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

示例 1:

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

示例 2:

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

算法1：

 使用python3, 用了额外的空间集合 set()，所以不符合题目要求

class Solution: def singleNumber(self, nums: List[int]) -> int: cnt = set() for i in nums: cnt.add(i) return (3 * sum(cnt) - sum(nums))//2

算法2：

使用位运算.

这个题其实就是求，在其他数都出现k次的数组中有一个数只出现一次，求出这个数。

而上面那个k次的是有通用解法的。

用一个32维的数组，访问原数组中的数，用这个32维的数组存储这些数里面第0位1的个数，第1位1的个数。。。第31位1的个数。

假如第0位1的个数是k的倍数，那么要求的这个数在该位一定是0，若不是k的倍数，那么要求的这个数在该位一定是1，第1位的1一直到第31位的1的个数同理。

class Solution { public: int singleNumber(vector<int>& nums) { vector<int>value(32); for(int i=0; i<nums.size(); i++) { int flag = 1; for(int j=0; j<32; j++) { if(j!=0) flag = flag << 1; if((flag & nums[i]) != 0) value[j] ++; } } int cnt = 0; int flag = 1; for(int i=0; i<32; i++) { if(i!=0) flag = flag << 1; if(value[i] % 3 != 0) cnt = cnt ^ flag; } return cnt; } };

算法3：

参考：Leetcode 137：只出现一次的数字 II（最详细的解法！！！）