只出现一次的数字 Single Number
题目
找出数组中只出现一次的数字
以下为详细说明：
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
https://leetcode-cn.com/problems/single-number/
思路&题解
要找出数组内元素，并且只出现一次的，可以想到需要对数组进行遍历，将出现的元素放入到哈希表内，统计每个不同元素出现的个数，最后把只出现一次的元素取出即为题解。
public int singleNumber(int[] nums) {
HashMap<Integer, Boolean> map = new HashMap<>();
for (int n : nums) {
if (map.containsKey(n)) {
// 第二次出现
map.put(n, true);
} else {
// 第一次出现
map.put(n, false);
}
}
int result = nums[0];
for (Map.Entry<Integer, Boolean> entry : map.entrySet()) {
if (entry.getValue()) {
continue;
}
result = entry.getKey();
break;
}
return result;
}
但是这个思路不满足题目，算法中使用map存储元素，和判断元素是否存在，不满足线性复杂度和不使用额外存储空间。
另一个思路是现对数组元素做排序，由于题干明确表示，数组内除了目标元素，其他都出现了两次，因此我们可以判断排序后的数组中，相邻元素不相等的即为答案。
所以需要找出一个线性复杂度的排序算法，然后还不能使用额外的存储空间。 这个就更困难了，时间复杂度满足线性的排序算法，也比较少，搜索一下可知，桶排序,计算排序满足O(n)，其他还有算法是O(nlogn)，O(n^2)的。
更优算法
实际上，本题的已知的最佳解法是利用位运算，结合输入数组的规律，一次遍历即可将重复的元素归零。
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i = 0; i < nums.length; i++) {
result = result ^ nums[i];
}
return result;
}
}
知识点分析
下面看一些位运算的基本规律，和一些可以记忆的延伸的定律，方便后续类似问题使用。
位的异或运算
也可以把异或运算叫做不进位加法，异或运算的核心是：相同为假，不同为真。
用0，1举例就是，0^0=0，1^0=1,1^1=0
进一步我们可以得到，相同两个数异或等于0，还可以得出一些交换率，比如A^B=B^A
记住两个常用的推理结论：
- 归零率，相同两个数异或后为零
- 零和任意数进行异或还是原数字
- 交换率，两个数异或顺序可以交换
这两个规律的一个使用场景是，交换两个数的值，除了引入一个中间变量，还可以连续异或运算：
void swap(int a, int b) {
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
本题的解法也是利用了这两个规律。
将数组内所有元素做异或，根据交换率，其中出现两次的相同元素异或后为零，最后剩下的就是0，0和目标元素异或，结果仍然是目标元素。