Question
Formatted question description: https://leetcode.ca/all/136.html
136 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?
Algorithm
Set
The direct idea is to use HashSet to use its constant search speed. Traverse each number in the array, if the current number is already in the HashSet, remove the number in the HashSet, otherwise add it to the HashSet.
This is equivalent to offsetting two by two. In the end, all the numbers that appear twice are removed from the HashSet, and the only one left is a single number.
Bit
Since numbers are stored in binary in the computer, each bit is 0 or 1. If we XOR two identical numbers, the exclusive OR of 0 and 0 is 0, and the exclusive OR of 1 and 1 is also 0.
Then if we XOR all the numbers in the array, and each pair of the same number will get 0, and then the last remaining number is the number that has only one time.
- num^num = 0
- careful about the initiation of sum, it should be 0
- just use a simple test case to find it out
Code
Java
public class Single_Number {
public class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int a = nums[0];
for (int i = 1; i < nums.length; i++) {
a ^= nums[i];
}
return a;
}
}
}