位运算题-----力扣上的题

前言：

这些题主要运用异或的性质，所以也就讲这个东东：

1. 异或的性质
   两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是
   如果同一位的数字相同则为 0，不同则为 1

2. 异或的规律
   任何数和本身异或则为 0
   任何数和 0 异或是 本身

3. 异或满足交换律。 即 a ^ b ^ c ，等价于 a ^ c ^ b

例题：

NO.1
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路：把全部元素异或起来，相当于只留下单个的那个数字，因为相同的数字异或结果为0，而与0异或终究等于其本身

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto i:nums){
            ans^=i;
        }
        return ans;
    }
};

NO.2
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路：这里的话也是遍历每一个数的所有二进制位，然后把每一位二进制位对应的1加起来，最后总数对3取模，如果有剩余，就证明那个数就符合题目中说的只有一个数字的那个数字。

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0;i < 32;++i){
            int sum = 0;
            for(int j = 0;j < nums.size();++j){
                sum += (nums[j] >> i) & 1;
            }
            res += (sum % 3) << i;
        }
        return res;
    }
};

NO.3
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

思路：先把所有数字异或起来，这样就得到ans=a^b，其中a,b就是我们要求的两个值，然后再用lowbit()求出最后二进制1代表多少(代码中是dis),然后用dis遍历数组元素，找出&dis有关的数字异或起来，这样就得到了其中一个答案，最后再用ans ^ 这个答案，就求出另外一个答案

这里有个细节：放眼到二进制，我们要找的这两个数字是不同的，所以它俩至少有一位是不同的，所以我们可以根据这一位，把数组分成这一位都是 1 的一类和这一位都是 0 的一类，这样就把这两个数分开了

那么怎么知道那两个数字哪一位不同呢？

回到我们异或的结果，如果把数组中的所有数字异或，最后异或的结果，其实就是我们要找的两个数字的异或。而异或结果如果某一位是 1，也就意味着当前位两个数字一个是 1 ，一个是 0，也就找到了不同的一位。

代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto i:nums){
            ans^=i;
        }
        int dis = ans&(-ans);
        int x  = 0;
        for(auto i:nums){
            if(dis & i){
                x^=i;
            }
        }
        return {x,ans^x};
    }
};

这里有个解决这种问题的模板

//实现解决 除了一个数字以外，其余数字都出现 m 次 的通用问题
class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }
}

---

---

例题：

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

思路：用数组第i位的符号位标记是否存在i+1.
第一次遍历, 找到重复数 —— 若置位前, 发现已经存在(即已经是负数), 则说明该数是重复数.
第二次遍历, 找到缺失的数.

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int less = 0, more = 0;
        for(int i = 0; i < nums.size(); i++){//使用符号位作为存在的标志
            int val = abs(nums[i]);
            if(nums[val - 1] < 0)//该数已经出现过
                more = val;
            else
                nums[val - 1] *= -1; //标记
        }
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > 0)//该数未出现过
                less = i + 1;
        }
        return {more, less};
    }
};

另外一种解法

异或解法
请点击！