LeetCode(136)只出现一次的数字

今天要练习的题目是：力扣（LeetCode)的第 136 题，只出现一次的数字

题目要求

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例：

输入：nums = [2,2,1]
输出：1

输入：nums = [4,1,2,1,2]
输出：4

提示：

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
除了某个元素只出现一次以外，其余每个元素均出现两次。

解题思路

这道题小呆首先想到的是哈希集合，因为题目中讲到：除了某个元素只出现一次以外，其余每个元素均出现两次。所以我们不能直接数组去重，但是我们可以利用Set集合存储的值唯一这个特性，去遍历数组，如果遍历过程中哈希集合中存储过当前项，那说明当前元素不唯一，直接删掉。循环结束后，就得出了那个不唯一的元素。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let hasSet = new Set()
  for (let i = 0; i < nums.length; i++) {
    if (hasSet.has(nums[i])) {
      hasSet.delete(nums[i])
    } else {
      hasSet.add(nums[i])
    }
  }
  return [...hasMap][0]
}

但是上面这种解法的空间复杂度为O(n)，而题目要求的空间复杂度为O(1)，所以不合符题意。然后小呆没有其他思路了，去看了题解的思路：

位运算中的异或运算XOR有几个特点
- 一个数和0做XOR运算等于本身：a⊕0 = a
- 一个数和其本身做XOR运算等于0：a⊕a = 0
- XOR运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
故而在以上的基础条件上，将所有数字按照顺序做抑或运算，最后剩下的结果即为唯一的数字
时间复杂度：O(n)O(n)，空间复杂度：O(1)O(1)

异或运算`XOR`

异或运算XOR属于位运算符，也就是在操作的过程中，会将十进制的数字转换成二进制，然后按照二进制的位来操作数值。小呆对于位运算也不是很熟悉，所以拿出《JavaScript 高级程序设计第 3 版》一起学习一下吧。位运算符位于书中第三章 3.5 节。

按位异或操作符由一个插入符合^表示，也有两个操作数。

按位异或操作在两个数值对应位上只有一个 1 时才返回 1，如果对应的两位都是 1 或都是 0，则返回 0。举个例子：十进制10，用二进制表示为1010（取 4 位），十进制0，用二进制表示为0000(取 4 位)。我们用表格来展示10 ^ 0 = 10，这就让我们明白了上面的思路 1：n ^ 0 = n

第一个数值的位	第二个数值的位	结果
0	1	1
0	0	0
0	1	1
0	0	0

再看另一个例子：10 ^ 10 = 0，这就让我们明白了上面的思路 2: n ^ n = 0

第一个数值的位	第二个数值的位	结果
1	1	0
0	0	0
1	1	0
0	0	0

老规矩，用一张动图来辅助理解思路 3：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ans = 0
  for (let num of nums) {
    ans ^= num
  }
  return ans
}