The question: Single Number
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?
My analysis:
This problem could be solved in two very tricky ways.
At here, I only use "XOR" method, and I would discuss the methond of using "digits counting" later.
The key idea: the property of XOR.
x ^ x = 0
x ^ y ^ x = y (the order could in random arrangement)
Thus for this problem. Since we have only one number appear once, other number apper perfectly twice.
we XOR all numbers in the array, and we would finally get the number that only appears once.
int ret = A[0];
for (int i = 1; i < A.length; i++) {
ret ^= A[i];
}
My solution:
public class Solution {
public int singleNumber(int[] A) {
if (A.length == 0 || A == null)
return 0;
int ret = A[0];
for (int i = 1; i < A.length; i++) {
ret ^= A[i];
}
return ret;
}
}
The question: 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?
My analysis:
This problem involvs many skills in mainpulating on a Integer.
The basic idea is:
The single number's each digit would only appear once, while other number's each digit would appear third times.
We count the appearance of each digts of all number in the array, then the digit does not appear times of three is a digit of the single number.
The skills in implementation:
1. how to get a interger's binary representation.
1.1 we need first have a interger array int[32] to record the appearance for each digit.
1.2 we use "digit" operator to move the target digit to the last digit, and use '&' to get the digit.
for (int i = 0; i < 32; i++) { //elegant while loop
for (int j = 0; j < A.length; j++) {
num[i] += (A[j] >> i) & 1;
}
}
Note: if we want to get the digit at i, we move it rightward i-1 digits. Note here num[i] is the counter the digits appear
at i+1 th position. 2. how to recover the integer from digits?
for (int i = 0; i < 32; i++) {
ret += (num[i] % 3) << i;//note the num[i] store the digit at position i+1.
}
My solution:
public class Solution {
public int singleNumber(int[] A) {
int[] num = new int[32];
int ret = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < A.length; j++) {
num[i] += (A[j] >> i) & 1;
}
}
for (int i = 0; i < 32; i++) {
ret += (num[i] % 3) << i;
}
return ret;
}
}