136. 只出现一次的数字¶
难度：简单
题目¶
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1：
输入: [2,2,1]
输出: 1
示例 2：
输入: [4,1,2,1,2]
输出: 4
题解¶
基本思路： 异或运算具有如下性质：
- 交换律：
a ^ b = b ^ a - 结合律：
(a ^ b) ^ c = a ^ (b ^ c) - 若
a ^ b = c，则a ^ c = b、b ^ c = a a ^ a = 0
根据性质1、2，异或运算的结果与参与运算的所有数值的排列顺序无关。根据性质3、4，相同整数的异或值为0，0与任何数异或仍为该数。因此将数组中各元素进行按位异或，得到的结果即为只出现一次的数值。
代码如下：
int singleNumber(int* nums, int numsSize){
int ret = 0, i = 0;
for (i = 0; i < numsSize; i++)
ret ^= nums[i];
return ret;
}