面试题 17.19.消失的二个数字-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:13:53

6900

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1、在1~N所有整数中，缺少了两个数字

2、时间复杂度为O(N)，空间复杂度O(1)

二、算法原理

解法：位运算

nums代表数组中所有元素的和，1~N代表1~N内所有元素的和，当nums加上a、b时，总和与1~N的总和相同，将所有的数异或到一起(在1~N和nums中a、b只出现一次)，结果tmp=a^b

由于^运算符类似无进位加法，即二进制第x位为1，a的二进制第x位为0，b的二进制第x位为1，然后分组异或

三、代码示例

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums)
    {
        int n = nums.size()+2;
        int tmp = 0;
        for(auto e : nums) tmp ^= e;
        for(int i = 1;i<=n;i++) tmp ^= i;
        int diff = 0;
        while(1)
            if(((tmp>>diff) & 1) == 1) break;
            else diff++;
        int a = 0,b = 0;
        for(auto e : nums)
            if(((e>>diff) & 1)==1) b^= e;
            else a^=e;
        for(int i = 1;i<=n;i++)
            if(((i>>diff) & 1)==1) b^=i;
            else a^=i;
        return {a,b};
    }
};