每日一练：位运算-消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

题目要求：

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

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

示例 1:

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

示例 2:

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

提示：

• nums.length <= 30000

按比特位分类 O(N)：

        现根据每日一练：位运算-丢失的数字-CSDN博客中的异或解法得到两个数字的异或结果，因为异或是相同为0，相异为1，就可以找到两个数字不一样的某个比特位。

        根据这个比特位可以将nums和[1,n]分为两类：该位置为0的数字和该位置为1的数字，这样做的话两类都只包含1个缺失的数字了。

        每个缺失的数字可以再使用异或解法得到。

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size() + 2;int two_dig_or = 0;for (const int x : nums)two_dig_or ^= x;for (int i = 1; i <= n; i++)two_dig_or ^= i; // 两数之异或int j = 0; // two_dig_or第一次出现1的位置while (((two_dig_or >> j) & 1) == 0)j++;int a = 0, b = 0;for (int i = 1; i <= n; i++)if ((i >> j) & 1)a ^= i;elseb ^= i;for (const int x : nums)if ((x >> j) & 1)a ^= x;elseb ^= x;return vector<int>({a, b});}
};