给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2] 输出: 3示例 2:
输入: [0,1,0,1,0,1,99] 输出: 99
解法一： 参考@Ant的思路
//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < 32; i++) {
int mask = 1 << i;
int count = 0;
for(int num : nums) {
if(num & mask) count++;
}
if(count % 3 != 0) res |= mask;//0或1
}
return res;
}
};解法二：
//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = 0, b = 0;
for(int num : nums) {
b = (num ^ b) & ~a;
a = (num ^ a) & ~b;
}
return b;
}
};解法一：
对于数组中的每一个数，都是一个32位的二进制位，数组中所有元素在某一位上的和必定是3n或者是3n+1。我们就统计出和是3n+1的位，这些位置1就是只出现1次的数了。
解法二：
将a看作是高位，b看作低位，这两个位组成的数到3时重置为0，就抵消掉出现次数为3的数了，最后剩下的单个数存在b中。
2019/12/06 13:14