leetcode-面试题 17.19 消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode） (leetcode-cn.com)

题意

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

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

思路

利用异或的性质，可以先将数组的所有数字和1~N的所有数字一起异或，得到一个数字X。安装相同的数字异或为0，那么X一定是缺失的两个数字的异或。那么这个数字的二进制中的1一定是属于其中某一个数字，不会属于相同数字。那么我们取得数字X二进制中最右边一个1的位置k，那么将数组的数字和1~N分组异或，按照每个数字的二进制在位置k是否也是1分组，最后得到的两个数字则为缺失的数字

代码

//
// Created by cb on 2021/12/21.
//

#include "vector"
#include "algorithm"
using namespace std;

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int mask = 0;
        int n = nums.size();
        for(int i = 1; i <= n+2+n; i++){
            mask ^= nums[i-1];
            if(i <= n+2)
                nums.push_back(i);
        }
        int xx = mask&(-mask);
        int a=0,b=0;
        for(auto &x: nums){
            if(xx&x) a^= x;
            else b ^= x;
        }vector<int> ans{a,b};
        return ans;
    }
};