[LeetCode 137] Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Diffculty
Medium

Similar Problems
[LeetCode ] Single Number II Medium [LeetCode ] Single Number III Medium [LeetCode ] Missing Number Medium [LeetCode ] Find the Duplicate Number Hard [LeetCode ] Find the Difference Easy

Analysis

由于x^x^x = x，无法直接利用I的方法来解。但可以应用类似的思路， 即利用位运算来消除重复3次的数。以一个数组[14 14 14 9]为例，将每个数字以二进制表达：

1110 1110 1110 1001

4331 对每一位进行求和 1001 对每一位的和做%3运算，来消去所有重复3次的数

class Solution { public: int singleNumber(vector &A) { int n = A.size(); int res = 0; for(int i = 31; i >= 0; i--) { int sum = 0; int mask = 1<<i; for(int j = 0; j < n; j++) { if(A[j] & mask) sum++; } res = (res << 1) + (sum % 3); } return res; } };

class Solution { public: int singleNumber(int A[], int n) { int bitnum[32] = {0}; int res=0; for(int i = 0; i < 32; i++){ for(int j = 0; j < n; j++){ bitnum[i] += (A[j] >> i) & 1; } res |= (bitnum[i] % 3) << i; } return res; } };

class Solution { public: int singleNumber(vector &A) { int p = 0; int q = 0; for(int i = 0; i < (int)A.size(); i++){ p = q & (p ^ A[i]); q = p | (q ^ A[i]); } return q; } };