Single Number
LeetCode.136. Single Number Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.You must implement a solution with a linear runtime complexity and use only constant extra space.
Example:
Input: nums = [4,1,2,1,2]
Output: 4
First Solution
public int singleNumber(int[] nums) {
int index = -1;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++){
if(map.get(nums[i]) == null){
map.put(nums[i],0);
}else {
map.remove(nums[i]);
}
}
// This has only one element
for (Integer i:map.keySet()) {
index = i;
}
return index;
}
Other Solution
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (Integer i : nums) {
Integer count = map.get(i);
count = count == null ? 1 : ++count;
map.put(i, count);
}
for (Integer i : map.keySet()) {
Integer count = map.get(i);
if (count == 1) {
return i;
}
}
return -1; // can't find it.
}
Better Solution
public int singleNumber(int[] nums) {
int index = nums[0];
if (nums.length > 1) {
for (int i = 1; i < nums.length; i++) {
index = index ^ nums[i];
}
}
return index;
}
a^b^a = a^a^b = b0^* = *异或运算