Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
public int singleNumber(int[] A) {
int x = 0;
for (int a : A) {
x = x ^ a;
}
return x;
}
Single Number II
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
逐位相加解題思路
To solve this problem using only constant space, you have to rethink how the numbers are being represented in computers -- using bits.
If you sum the ith bit of all numbers and mod 3, it must be either 0 or 1 due to the constraint of this problem where each number must appear either three times or once. This will be the ith bit of that "single number".
A straightforward implementation is to use an array of size 32 to keep track of the total count of ith bit.
初代粗糙版本
public int singleNumber(int[] A) {
int[] bits = new int[32];
for (int i = 0; i < 32; i++) {
for (int j = 0; j < A.length; j++) {
bits[i] += (A[j] >> i) & 1;
}
}
int result = 0;
for(int i=0; i<32; i++) {
result += (bits[i] % 3) << i;
}
return result;
}
改的精致一點
public int singleNumber(int A[]) {
if (A == null || A.length < 4) {
return -1;
}
int bits[32] = {0};
int result = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < A.length; j++) {
if ((A[j] >> i) & 1) {
bits[i]++;
}
}
result |= ((bits[i] % 3) << i);
}
return result;
}
