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?
Example :
Input : [1 2 2 3 1]
Output : 3
Method:
a ^ a = 0, we can keep XOR the numbers, the final result is the single number.
Solution:
Time: O(n) Space: O(1)
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int singleNumber(final List<Integer> A) {
int single = 0;
for (int i : A) {
single = single ^ i;
}
return single;
}
}
class Solution {
public int singleNumber(int[] nums) {
int xor = nums[0];
for (int i = 1; i < nums.length; i ++) {
xor ^= nums[i];
}
return xor;
}
}