136-只出现一次的数字.md

136-只出现一次的数字

题目信息

题目地址： 只出现一次的数字

题目内容：

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

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

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

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

题解

解法一

思路：

可以使用set来实现，遍历数组，如果set中存在该元素，就删除该元素，否则就将该元素放入set中

最终set中就只有一个元素，就是只出现一次的元素

代码实现：

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

解法二

思路：

使用异或，根据异或的特点可以排除重复的元素，异或的特点如下

1、任意数与0进行异或，结果仍是原数(a ^ 0 = a)

2、任意数与其自身进行异或，结果是0(a ^ a = 0)

3、异或运算满足交换律和结合律，也就是说无论数字的顺序如何，异或的结果都是相同的，例如(a ^ b ^ a)就等价于(a ^ a ^ b) = b

本题中，数组中数字的顺序不会影响最终结果，那么不管这些成对的数字出现在数组中的哪个位置，它们最终都会相互抵消，留下的就是那个唯一的、未成对的数字

代码实现：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    if(nums.length === 1) return nums[0]
    let res = 0
    for(let i = 0; i < nums.length; i++) {
        res ^= nums[i]
    }
    return res
};

更简便的写法：

使用reduce方法也可以写出更简便的写法

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    if(nums.length === 1) return nums[0]
    return nums.reduce((prev, cur) => prev ^ cur, 0)
};