LeetCode 136 和 XOR

主要借助这个机会简单说下 XOR ( 异或 ) 运算

XOR

对于一个二进制位来说 ——

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

直观理解, 杀掉两个一样的比特,不一样的保留

那么有些很显然的性质可以推到 ——

• 交换律 a ^ b = b ^ a
• 结合律 (a ^ b) ^ c = a ^ (b ^ c)
• a ^ a = 0
• a ^ 0 = a

题解

题目说明

给定一个非空整数数组 nums。

数组中满足：

• 除了某个元素只出现一次以外
• 其余每个元素都恰好出现两次

要求找出这个只出现一次的元素。

题目分析

第一反应是哈希表,做一个元素->出现此处的映射即可,但是显然空间复杂度不符合 O(1) 的要求了

「其余每个元素恰好出现两次」,那上面说了直观理解 —— 「两个一样的直接杀」,恰好符合 XOR 的优雅性质

好,现在想手上有三个数据 a, a, b, 两个 a 可以通过 XOR 运算变成 0, 然后 b ^ 0 = b, 所以我们只需要把序列的各个元素做异或运算即可 (同时不管给出的三个元素怎么排列都可以利用交换 / 结合律来变成最好看的样子)

那么现在假设数组中有 k 对重复元素时,全部异或后的结果为0,然后再和孤单的元素进行 XOR 得到 最终答案

再推广到 k + 1 对重复元素的时候, 由于新的这一对元素 XOR 结果为 0, 而 0 和 k 组重复元素的情况再进行一次 XOR 运算结果还是 k 组重复元素的情况的结果.

因此当 k + 1 对重复元素的时候依旧成立,那么由归纳法可得到无论存在多少对重复元素,只要它们都恰好出现两次,所有元素 XOR = 唯一出现一次的元素

边界情况也非常好分析,略(

总结

主要是想顺带写下 XOR 运算特性, 不过具体的位运算使用和设计等挖坑,未来可期