[136] 只出现一次的数字

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

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

根据题目，我们很直观的想出：可以利用hash表的方式存储第一次得到的值，之后每次查询hash表看是否有相同的值，若有则删除。遍历结束后hash表中剩下的值即为所求。

这样做时间复杂度O(n)，空间复杂度O(n)。

var singleNumber = function(nums) {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    if (hash[nums[i]] === undefined) {
      hash[nums[i]] = nums[i];
    } else {
      Reflect.deleteProperty(hash, nums[i]);
    }
  }
  return hash[Reflect.ownKeys(hash)[0]];
};

当然也可以利用排序后的数组相邻的值若不同则可得唯一性来解，这样的时间复杂度O(nlgn)，空间复杂度O(1)。这里就不多说了。

但由于题目要求时间复杂度O(n)，空间复杂度O(1)，因此不能使用排序算法，也不能使用hash-table。

本题使用二进制异或的性质来完成：两个数字异或 a^b 是将 a 和 b 的二进制每一位进行运算，如果同一位的数字相同则为0，不同则为1。

var singleNumber = function(nums) {
  let res = 0;
  for (let i = 0; i < nums.length; i++) {
    res = res ^ nums[i];
  }
  return res;
};