LeetCode 136：只出现一次的数字 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?
示例 1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4解题思路：
- 排序数组，如果某个数与前后两个数均不相等则该数只出现一次。
- 哈希映射，key 为每个数的值，value 为每个数出现的频率。最后找到 value = 1 的数返回。
- 异或运算，直接进行异或操作求值。不使用额外空间。
异或运算（XOR）解题是最优雅的解法，且不使用额外空间，其概念为：
-
如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位
- a XOR 0 = a
-
如果我们对相同的二进制位做 XOR 运算，返回的结果是 0
- a XOR a = 0
- XOR 满足交换律和结合律
代码：
借助哈希表：
Java:
哈希映射频率（可用于字符串出现频率的计算）
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
Integer count = map.get(num); //get() 方法获取元素不存在时返回null
count = count == null ? 1 : ++count; //count为null 时证明元素不存在，则频率改为1，否则count频率+1
map.put(num, count); //加入映射表
}
for (Integer num : map.keySet())
if (map.get(num) == 1) return num; //返回频率为1的数
return 0;
}
}Python：
1、借助 try...except...，只适用于该题中重复元素重复出现次数为偶数次。
class Solution(object):
def singleNumber(self, nums):
hash_map = {}
for i in nums:
try:
hash_map.pop(i) # 尝试移除该数
except:
hash_map[i] = 1 # 移除失败证明字典内没有该值，则添加到字典
return hash_map.popitem()[0] #最后字典中只剩下一个键值对，返回其键值2、字典映射频率（可用于字符串出现频率的计算）
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hash_map = {}
for num in nums:
hash_map.setdefault(num, 0)
hash_map[num] += 1 # 每次出现频率加一
for k, v in hash_map.items(): #二次遍历返回频率为1的数
if v == 1:
return k
return 0亦或运算(XOR)：
其处理逻辑可以简单理解为：
输入: [2 , 3 , 2 , 4 , 3] , 初始化 result = 0
result = 0 XOR 2 = 2
result = 2 XOR 3 = [2 , 3]
result = [2 , 3] XOR 2 = 3
result = 3 XOR 4 = [3 , 4]
result = [3 , 4] XOR 3 = 4
返回 result = 4异或运算是位操作中最基本运算之一，以上是为方便理解异或运算而简化抽象的逻辑，如果想进一步了解位操作可以参考Wiki百科。
高级程序设计语言异或运算表示符号一般是 ^。
Java:
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums)
result = result ^ num;
return result;
}
}Python:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
result = result ^ num
return result
