Easy
Given a non-empty 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 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
Solution
Actually it’s quite simple to solve, but we should make clear that it requires O(N) complexity and no extra memory usage. So we need to find out the single one during several iterations.
As is well-known,
a XOR a = 0
0 XOR a = a
So all the duplicate numbers will be calculated to 0 after looping xor, and the result of the iteration of xor must be the single number value.
Here is the sample code:
class Solution:
def single_number(self, nums: List[int]) -> int:
# xor each sibling num
return reduce(lambda a, b: a ^ b, nums)
public class SingleNumber {
public int singleNumber(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[0] ^= nums[i];
}
return nums[0];
}
}
Complexity Analysis
Time complexity of this approach is O(N);
Space complexity is O(1);
Forgive my poor English, I just wanna improve my writing skill.
So if I make some stupid mistakes in writing, forget about them.
Let's focus on the code :)