136_只出现一次的数字

难度：简单

题目

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

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例一：

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

示例二：

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

这道题最直观的方法就是用 hash 表存储每个出现的数字和出现的次数，最后返回出现一次的数字。或者使用集合，用集合来存储数字，如果集合中没有该数字就加入，如果有就删除，最后剩下的数字就是只出现一次的数字。

考虑到不使用额外空间来实现，可以用位计算来解决。异或运算有以下三个性质：

$a\otimes a=0$
$a\otimes 0=a$
$a \otimes b \otimes a =b\otimes a \otimes a = b \otimes (a\otimes a) = b \otimes 0 = b$

所以可以对数组里的全部元素进行异或，最后得到的值就是只出现一次的数

public int singleNumber(int[] nums) {
  int ans = 0;
  for (int num: nums){
    ans ^= num;
  }
  return ans;
}

Leetcode

leetcode