xzySolitaire
BAN USERFor this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.
The algorithm looks like this:
List<Integer> result = new ArrayList<Integer>();
int temp = num[0];
for (int i = 1; i < num.length; i++) {
temp ^= num[i];
}
for (int i = 0; i < 32; i++) {
int t = 0;
if ((1 << i) & temp == (1 << i)) {
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
result.add(t);
if (result.size() == 3) {
break;
}
}
}
return result;
Okay then... This is such a nightmare question for non-native speakers... I really got no clues without checking the answers...
- xzySolitaire October 26, 2014
For this question, I think we can do it in O(n) time.
- xzySolitaire November 17, 20141. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.
The algorithm looks like this:
List<Integer> result = new ArrayList<Integer>();
int temp = num[0];
for (int i = 1; i < num.length; i++) {
temp ^= num[i];
}
for (int i = 0; i < 32; i++) {
int t = 0;
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
result.add(t);
if (result.size() == 3) {
break;
}
}
return result;