每日OJ题_位运算⑦_力扣面试题 17.19. 消失的两个数字

目录

力扣面试题 17.19. 消失的两个数字

解析代码

力扣面试题 17.19. 消失的两个数字

面试题 17.19. 消失的两个数字

 难度 困难

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

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

示例 2:

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

提示：

• nums.length <= 30000

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {

    }
};

解析代码

        困难题，但之前写过找一个单身狗和找两个单身狗的了，转化成找两个单身狗（力扣260），再转化成找一个单身狗（力扣136）（力扣268）：

异或(^)运算的运算律（解决只出现一次的数字（单身狗）问题）
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ ( b ^ c)

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for(int i = 1; i <= n + 2; ++i)
        {
            nums.push_back(i); // 转换成找两个单身狗->力扣260
        }
        n = nums.size();
        for (int i = 0; i < n; i++)
        {
            sum ^= nums[i];
        }
        int count = 0;
        for (int i = 0; i < 32; i++)
        {
            if (sum & 1 << i) //循环判断第几位是1
            {
                count = i;//如果是1 记录下来
                break;
            }
        }
        int a = 0, b = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] & 1 << count)
                a ^= nums[i];
            else
                b ^= nums[i];
        }
        return {a, b};
    }
};