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?
题意：数组中只有一个数字出现了一次，其他都是成对出现的，求这个只出现了一次的数字。
思路：
这道题用哈希map或者哈希set都可以，但是需要额外的存储空间。
不需要额外存储空间的方法是位运算，用位运算异或的特性，相同数字异或为0，所有数组中成对出现的数字最后异或以后都是0，所以最后异或所有数字的结果就是那个只出现了一次的数字。
//哈希set
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0 || nums.length % 2 == 0) {
return 0;
}
int res = 0;
HashSet<Integer> set = new HashSet<>();
for (int i : nums) {
if (!set.add(i)) {
set.remove(i);
}
}
for (Integer i : set) {
res = i;
}
return res;
}
//位运算
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0 || nums.length % 2 == 0) {
return 0;
}
int res = 0;
for (int i : nums) {
res ^= i;
}
return res;
}