位运算问题-LeetCode 136、137、260（只出现一次的数，异或运算）
位运算问题-LeetCode 136、137、260（只出现一次的数，异或运算）
【LeetCode #136】只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1
解题思路：
异或的性质： 其基本性质为，相同为1，不同为0. 满足交换律，结合律，分配律，并且还有三个很重要的应用方面。
- 自反性质：a ^ b ^ b = a ^ 0 = a
- 交换两个数：a = a ^ b; b = a ^ b; a = a ^ b;
- 判断两个数是否相等：a ^ b == 0
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < nums.size(); i++){
res ^= nums[i];
}
return res;
}
};使用hashmap将每个数字对应的个数存入哈希表中，然后遍历整个数组进行检查！
class Solution {
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
【LeetCode #137】只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2] 输出: 3
解题思路：
关于异或，或，非运算有以下性质： 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.
class Solution {
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;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-number-ii
【LeetCode #260】只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。 示例 :
输入: [1,2,1,3,2,5] 输出: [3,5]
注意： 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
解题思路：
根据异或的性质，如果数组中只有两个数出现次数为1，分别为A和B，其他出现次数为2，那么首先第一步直接对所有数据进行异或，最终会得到A^B的结果！ 接着寻找A^B位数为1的地方，通过flag << 1得到，这样就可以将整个数组分成两个部分，第一部含有所有num&flag = 1的数，另一部分含有所有num&flag = 0的数。 最后分别对这两部分使用异或既可了，参考于LeetCode #136
class Solution {
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){
result[0] ^= num;
}else{
result[1] ^= num;
}
}
return result;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-number-iii
腾讯云开发者
