算法实战：位运算解决整数求和、唯一数与缺失数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 方法一：排序 (时间复杂度较大:O(NlogN)，但容易想到)
        // sort(nums.begin(), nums.end());
        // for(int i = 0; i < nums.size() - 1; i += 3) {
        //     if(nums[i] != nums[i + 1]) {
        //         return nums[i];
        //     }
        // }
        // return nums.back();

        // 方法二：位运算 (为线性时间复杂度:O(32N)，但非常巧妙比较难想)
        int ret = 0; // 作为位图
        for (int i = 0; i < 32; i++) { // 一个数二进制位的长度，依次修改 ret 的每一位
            int sum = 0;
            for (int x = 0; x < nums.size(); x++) { // 计算 nums 中所有数的二进制第 i 位的和
                sum += ((nums[x] >> i) & 1);
            }
            ret |= ((sum % 3) << i); // 求和结果余 3 后修改到 ret 对应第 i 位的位置
        }
        return ret;
    }
};

流程解析

消失的两个数字

题目描述

给定一个包含从 0 到 n 的所有整数的数组，其中有两个数字消失了。找出这两个消失的数字。

题目示例

输入：nums = [1] 输出：[0, 2]

解法（位运算）

核心思路

本题相当于就是 268.丢失的数字 + 260.只出现一次的数字 III 组合起来的题。先将数组中的数和【1，n+2】区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了 260.只出现了一次的数字 III 这道题。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 位运算
        // 先将数组 nums 所有数以及 1~N+2 区间所有数全部异或一遍，得到消失两数的异或
        int ret = 0;
        int a = 0;
        int b = 0; // 分别表示两个消失的数

        for (int i = 0; i < nums.size(); i++) {
            ret ^= nums[i];
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }

        // 此时 ret = a ^ b
        // 由于 a 和 b 一定不同，所以一定会存在某一位比特位一个是 0 一个是 1
        // 两者异或后对应的那一位就一定是 1，所以我们需要找到那一位
        // 获取到 ret 最右侧出现 1 的比特位位置
        int x = 0;
        while (1) {
            if (((ret >> x) & 1) == 1) {
                break;
            }
            x++;
        }

        // 将数组 nums 所有数以及 (1~N+2) 区间所有数分成两类：
        // 一类就是第 x 位比特位值为 0，一类就是第 x 位比特位值为 1
        // 这样两个消失数就会被分开，通过异或，在数组以及 (1~N+2) 区间都出现的数就会抵消，
        // a 和 b 也就分别是这两个消失数了
        for (int i = 0; i < nums.size(); i++) {
            if (((nums[i] >> x) & 1) == 0) // 假设 a 是第 x 位比特位为 0 的消失数
                a ^= nums[i];
            else // 假设 b 就是第 x 位比特位为 1 的消失数
                b ^= nums[i];
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (((i >> x) & 1) == 0)
                a ^= i;
            else
                b ^= i;
        }
        // 两次循环则数组中存在的数异或了两次被抵消，a 和 b 就分别是两个消失数
        return {a, b};
    }
};

流程解析