LeetCode 136. 只出现一次的数字

136. 只出现一次的数字

题目描述

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

说明：

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

示例 1:

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

示例 2:

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

解题思路

思路一： 利用Map

利用hash表是可以解决， 但是空间复杂度是O(n)， 而且使用了额外空间。
既满足时间复杂度又满足空间复杂度，就要提到位运算中的异或运算 XOR

思路二： 按位异或操作符

先来看看按位异或操作符基本使用：

let a = 5;      // 00000000000000000000000000000101
a ^= 3;         // 00000000000000000000000000000011

console.log(a); // 00000000000000000000000000000110
// 6

console.log(a^a); // 00000000000000000000000000000000

let b = 7;      // 00000000000000000000000000000111
b ^= 0;         // 00000000000000000000000000000000

console.log(b); // 00000000000000000000000000000111
// 7

console.log(a^b^a); // 00000000000000000000000000000111
// 输出b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

可以看出异或运算有以下特点：

• 一个数与0做异或运算等于其本身： num1^0 = num1;
• 一个数与其本身做异或运算等于0： num1^num1 = 0;
• 异或运算满足交换律和结合律： num1^num2num1 = (num1^num1)num2 = 0^num2 = num2

根据题意其余每个元素均出现两次， 所以我们可以将所有数字按顺序做异或运算， 最后剩下的结果即为唯一的数字。
相当于将相同的数字先异或，这样两两异或就只剩0了，然后0再和最后的一个数字异或得到最终值。

实现代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let res = 0;
    for(const num of nums) {
        res ^= num;
    }
    return res;
}; 
1
2
3
4
5
6
7
8
9
10
11

• 时间复杂度：O(n), 其中n为给定数组的长度;
• 空间复杂度：O(1), 常数空间

或者不使用变量res， 利用nums[0]来存储结果。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let len = nums.length;
    for (let i = 1; i < len;i++) { 
        nums[0]^=nums[i]; 
    }
    return nums[0]
};
1
2
3
4
5
6
7
8
9
10
11

或者使用reduce方法实现：

var singleNumber = function(nums) { 
    return nums.reduce((prev, next) => prev^next, 0)
};
1
2
3

本题难点在于想到异或运算。

参考资料

画解算法：136. 只出现一次的数字 - 只出现一次的数字 - 力扣（LeetCode）