Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 - 30-Day LeetCoding Challenge
这是一个 leetcode 官方的小活动，地址在这里（如果被重定向回中文站了，去掉域名里的 -cn 即可）。活动内容很简单，从 4 月 1 号开始，每天会选出一道题（国内时间中午 12 点更新），在 24 小时内完成即可获得一点小奖励。虽然奖励似乎也没什么用，不过作为一个官方的打卡活动，小猪还是来打一下卡吧，正好作为每天下班回家后的娱乐。
这里是 4 月 1 号的题，也是题目列表中的第 136 题 -- 『只出现一次的数字』
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4EASY
这道题似乎没什么好讲的，大概是作为活动的开篇，预热一下，吸引围观，激励用户参与。
下面给出几个方案，供小伙伴们参考。
其实这是个凑数的方案（哈哈哈，没想到吧）。小猪相信不会有小伙伴们这么去写的，毕竟直接就到 O(n^2) 了，实在是太浪费了。权且作为最最基础的实现吧。
const singleNumber = nums => {
const arr = [];
for (const n of nums) {
const idx = arr.indexOf(n);
idx === -1 ? arr.push(n) : arr.splice(idx, 1);
}
return arr.pop();
};用 Set 代替了方案 1 中的数组，使得查询和删除都快了很多。不过代码还是太多了，并且也得基于额外的数据结构和空间，并不推荐。
const singleNumber = nums => {
const set = new Set();
for (const n of nums) {
set.has(n) ? set.delete(n) : set.add(n);
}
for (const x of set.keys()) return x;
};用位操作代替了前两种方案里对于额外数据结构和空间的依赖。小猪觉得这个方案算是这道题的标准实现吧，才不会告诉你前两种方案是为了写文章才凑出来的呢 hia hia hia O(∩_∩)O
稍微解释一下异或这个位操作吧，它的行为逻辑可以理解为两个值不同则为 true，相同则为 false。如下表：
0 ^ 0 === 0
0 ^ 1 === 1
1 ^ 0 === 1
1 ^ 1 === 0那么基于这个运算逻辑，我们可以发现，对于两个相同的数值进行异或运算，那么结果一定是 0。再看看我们题目中的数据，正好是成对的数字加上一个单独的数字。这时候再加上异或这个运算可以满足交换律和结合律，于是我们那些成对的数字运算完后正好为 0，而 0 与一个数字进行异或预算便是这个数字本身。
基于这个思路，我们可以得到如下的代码：
const singleNumber = nums => {
let ret = 0;
for (const n of nums) ret ^= n;
return ret;
};当然，都写成这样了，不如我们就直接一行吧：
const singleNumber = nums => nums.reduce((prev, cur) => prev ^ cur, 0);关于异或操作的一些实际应用场景，这里再补充几个栗子吧。
let a = 10;
let b = 20;
a = a ^ b;
b = b ^ a;
a = b ^ a;
console.log(a, b) // 20, 10稍微解释一下过程吧：
- 第一次异或操作得到了两个数字不同的位为 1，相同的位为 0，并保存进了变量
a。 - 第二次异或操作相当于是把
b中两个数不同的位取反，相同的位保持不变，于是 b 就变成了 a，然后保存进变量b中。 - 第三次异或操作继续把现在
b中两个数不同的位取反，相同的位保持不变。注意，这时候的b中的值其实是 a，所以运算后得到的值是 b，然后保存进变量a里。 - 最终 a 就进了
b，b 就进了a。
let a = 10;
let b = 20;
while (b !== 0) {
const a2 = a ^ b;
const b2 = (a & b) << 1;
a = a2;
b = b2;
}
console.log(a) // 30同理，不过这里面还用到了与操作和左移操作。原理其实和加法是一样的，就是按位相加，然后需要进位的地方就进位。不过在二进制中，可能的情况会比较少。具体如下：
- 通过异或运算找出按位相加后不会产生进位的地方。
- 通过与运算找出按位相加后会产生进位的地方，并做进位。
- 把上述两个值保存后继续执行相同的计算，直到加数减少为 0，那么被加数就变成了最初的两数之和。
这是 『30-Day LeetCoding Challenge』 的第一题，没有太多可以说的，于是就稍微拓展了一点关于异或操作的内容。希望可以帮到有需要的小伙伴。
如果觉得不错的话，记得『三连』哦。小猪爱你们哟~ >.<
