【算法题】28.只出现一次的数字

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

可以不使用额外空间来实现吗？

示例1

输入: [2,2,1]
输出: 1

示例2

输入: [4,1,2,1,2]
输出: 4

思路

    普通情况下在数组中找到元素出现次数，可以通过哈希表存储每个元素和该元素出现的次数。遍历数组即可得到每个元素出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的元素。

    数组中 个元素均出现两次，也可以使用集合存储出现过的元素，第一次出现加入集合，第二次出现从集合中删除该元素，最终得到集合中唯一的元素。

    这两种解法都需要使用 的空间，那么如何可以不使用额外空间呢？我们可以使用异或运算，异或运算的运算法则如下：

1. 归零律：

2. 恒等律：

3. 交换律：

4. 结合律：

5. 自反：

    数组中 个元素重复，假设 ，则数组中有 m 个数各出现两次，一个数出现一次。令 为出现两次的 m 个数， 为出现一次的数。数组中的全部元素的异或运算结果总是可以写成如下形式：

    因此，将所有数字按照顺序异或运算，最后剩下的结果即为唯一的数字 。

代码实现

int singleNumber(int* nums, int numsSize){
      int ret = 0;
      for(int i = 0; i < numsSize;i++){
           ret ^= nums[i]; 
      }
      return ret;
}