2014
03-28

# LeetCode-Single Number II[位运算]

### Single Number II

iven 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?

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2

int singleNumber(int A[], int n) {
int count[32] = {0};
int result = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < n; j++) {
if ((A[j] >> i) & 1) {
count[i]++;
}
}
result |= ((count[i] % 3) << i);
}
return result;
}

1. ones   代表第ith 位只出现一次的掩码变量
2. twos  代表第ith 位只出现两次次的掩码变量
3. threes  代表第ith 位只出现三次的掩码变量

ones = 101
twos = 0
threes = 0
--------------
ones = 0
twos = 101
threes = 0
--------------
ones = 0
twos = 0
threes = 101
--------------

int singleNumber(int A[], int n) {
int ones = 0, twos = 0, threes = 0;
for (int i = 0; i < n; i++) {
twos |= ones & A[i];
ones ^= A[i];// 异或3次 和 异或 1次的结果是一样的
//对于ones 和 twos 把出现了3次的位置设置为0 （取反之后1的位置为0）
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}

1. 后面的掩码变量部分乍一看比较难理解，其实就是把32位按照一个整体来看待。