First. 陈列一下“异或”的一些性质
异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。
它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。
性质
1、交换律
2、结合律(即(a^b)^c == a^(b^c))
3、对于任何数x,都有x^x=0,x^0=x
4、自反性 A ^ B ^ B = A ^ 0 = A
应用
一、交换两个整数的值而不必用第三个参数
a = 9;
b = 11;
a=a^b; 1001^1011=0010
b=b^a; 1011^0010=1001
a=a^b; 0010^1001=1011
a = 11;
b = 9;
二、奇偶判断
三、判断两个数是否相等
a ^ b == 0 ?
四、格雷码(Gray code)
五、奇数分频
Second. Leetcode136.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
代码解答如下:
/*给定一个非空整数数组 除了某个元素只出现一次以外 其余每个元素均出现两次 找出那个只出现了一次的元素 */ /*----------------------------------------头文件------------------------------------------------------*/ #include <iostream> #include <vector> #include <unordered_map> using namespace std; /*-------------------------------------使用异或的性质----------------------------------------------*/ class Solution1 { public: int singleNumber(vector<int>& nums) { int res = 0; for (int i = 0; i < nums.size(); i++) { res ^= nums[i]; //使用异或的性质,相同为0,不同为1. 0^X=X X^X=0 } return res; } }; /*-----------------------------------------使用哈希表-----------------------------------------------*/ class Solution2 { public: int singleNumber(vector<int>& nums) { unordered_map<int, int> mm; for (auto n : nums) { if (mm.count(n)) { mm[n]++; } else { mm.emplace(n, 1); } } for (auto n : nums) { if (mm[n] == 1) { return n; } } } }; /*--------------------------------------程序结束----------------------------------------------------*/
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number
Third. Leetcode136.只出现一次的数字Ⅱ
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number-ii
关于异或,或,非运算有以下性质:
0 ^ x = x, x ^ x = 0, x & ~x = 0, x & ~0 = x.
-
x第一个出现后,经过下面的程序可以得到 a = x, b = 0;
-
x第二次出现后,经过下面的程序可以得到 a = 0, b = x;
-
x第三次出现后,经过下面的程序可以得到 a = 0, b = 0;
而只出现一次的数字,经过程序得到a = x, b = 0; 所以最后函数返回值为a.
代码解答如下:
/* 给定一个非空整数数组, 除了某个元素只出现一次以外 其余每个元素均出现了三次 找出那个只出现了一次的元素 */ #include <iostream> #include <vector> using namespace std; class Solution2to1{ public: int singleNumber(vector<int>& nums) { int a = 0, b = 0; for (auto num : nums) { a = (a^num)&~b; b = (b^num)&~a; } return a; } };
Forth. Leetcode136.只出现一次的数字Ⅲ
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意:
结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number-iii
根据异或的性质
如果数组中只有两个数出现次数为1,分别为A和B,其他出现次数为2,那么首先第一步直接对所有数据进行异或,最终会得到A^B的结果!
接着寻找A^B位数为1的地方,通过flag << 1得到,这样就可以将整个数组分成两个部分,第一部含有所有num&flag = 1的数,另一部分含有所有num&flag = 0的数。
巧妙之处:
假如A 1001 B 1101
A^B = 0010
刚开始flag=1;通过while循环和左移<<1可以得到一个值 0010
而0010和上面A 和 B 分别按位与 得到1和0,这样就可以分成两个数组
代码解答:
/* 给定一个整数数组 nums 其中恰好有两个元素只出现一次 其余所有元素均出现两次 找出只出现一次的那两个元素 */ #include <iostream> #include <vector> using namespace std; class Solution3to1 { public: vector<int> singleNumber(vector<int>& nums) { int res = 0; for (auto num : nums) { res ^= num; } int flag = 1; while ((res & flag) == 0) { flag = flag << 1; } vector<int> result(2, 0); for (auto num : nums) { if (num & flag == 1) { result[0] ^= num; } else { result[1] ^= num; } } return result; } };
有问题欢迎留言互相交流学习哈!!!!