Given an array of integers, every element appears twice except for one. Find that single one.
We can use a hash set to record each integer‘s appearing time. Time complexity O(n), space cost O(n)
1 public class Solution { 2 public int singleNumber(int[] nums) { 3 Set<Integer> counts = new HashSet<Integer>(); 4 int length = nums.length, result = nums[0]; 5 for (int i = 0; i < length; i++) { 6 int tmp = nums[i]; 7 if (counts.contains(tmp)) 8 counts.remove(tmp); 9 else 10 counts.add(tmp); 11 } 12 for (int tmp : counts) 13 result = tmp; 14 return result; 15 } 16 }
The key to solve this problem is bit manipulation. XOR will return 1 only on two different bits. So if two numbers are the same, XOR will return 0. Finally only one number left.
1 public int singleNumber(int[] A) { 2 int x = 0; 3 for (int a : A) { 4 x = x ^ a; 5 } 6 return x; 7 }
原文：http://www.cnblogs.com/ireneyanglan/p/4809029.html