Single Number：
1. Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
代码：
class Solution {
public:
int singleNumber(int A[], int n) {
int result = 0;
for(int i = 0; i < n; ++i){
result ^= A[i];
}
return result;
}
};
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?
方法1：（分别计算各位1的个数 mod 3）
class Solution {
public:
int singleNumber(int A[], int n) {
int count[32] = {0};
int result = 0;
int bit = sizeof(int) * 8;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < bit; ++j){
if((A[i] >> j) & 0x1) count[j] = (count[j] + 1) % 3;
}
}
for(int i = 0; i < bit; ++i){
result |= (count[i] << i);
}
return result;
}
};
方法2:(三个变量，分别记录出现一次，出现两次，出现三次的值)
class Solution {
public:
int singleNumber(int A[], int n) {
int one, two, three;
one = two = three = 0;
for(int i = 0; i < n; ++i){
two |= (one & A[i]);
one ^= A[i];
three = ~(one & two);
one &= three;
two &= three;
}
return one;
}
};