异或
1)相同为0,不同为1。
2)满足交换律以及结合律
3)交换律:即不关心顺序
a ^ b = b^c;
4)结合律:优先级计算无关
(a ^ b) ^c = a ^(b ^c)
5) 0 ^ N = N; N ^N = 0; 即 偶数次数异或为0 奇数次异或为该奇数。
常用:
时间复杂度为O(N) 空间复杂度为O(1)的查找数字类型
Leetcode题:
1)136. 只出现一次的数字
思路:1.利用偶数次数异或为0性质,即 N ^ N = 0 以及结合律和交换律。
2.维护一个变量(这里是eor),循环异或数组中的数字即可。最后结果为出现次数为奇数的数字。
2)260. 只出现一次的数字 III
上一题的升级版本。此时出现了两个都出现奇数次数的数字 设为 a 和 b
思路:1.维护一个变量(eor) 遍历异或数组数字 取得 a ^ b 的结果 eor = a ^b;
2.a ^ b 意味着 在32位中 必定有一位 异或结果为 1 也就是说 a 和 b进行异或 肯定有一位是不相同的;
3.提取 a ^ b 最右边 1 的方法 eor & (~eor + 1) 即和自己的补码相与。设该数字为 x
4.根据 3.的结果 将 数组nums中每一个数字 分成两堆 即 与 x 相与相同 和 x相与不相同的两队;
5.通过 4. 可以得出 a 、 b 中的 一个 然后 将结果 与 eor相与 即 a ^ b ^b(这里假设得到b)
a ^b ^a(这里假设得到a)。即可得到结果
