[算法]——位运算（三）

[算法]——常见位运算总结

[算法——位运算（一）

[算法]——位运算（二）

目录

一、前言

二、正文

1.消失的两个数字

1.1 题目解析

1.2 算法原理

1.3 具体代码

三、结语

一、前言

        本文将为大家带来位运算中最后一道例题的讲讲，其难度也为困难级别，希望大家能够从中有所收获。

二、正文

1.消失的两个数字

消失的两个数字 -【 力扣】

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

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

示例1：

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

示例 2:

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

1.1 题目解析

        对于本题，要求我们能够从题目中所给的包含1到N的所有整数中找到缺失的两个数字

1.2 算法原理

位运算知识：

●两个相同的数异或结果为0，任何数与0异或结果为数本身                              

●通过将一个数与其相反数进行与运算可以求得二进制中最右边的1

       

具体步骤如下：

1.将所给数组与包含1至N的数组中所有的数进行异或，由于相同的数异或后结果为0，所以所得结果为缺失两个数字相异或后的结果，记为sum

2.通过将sum与其相反数进行与运算，找到二进制中最低位的那个1，即最右边的1，由于异或操作是相异为1，因此通过该位上二进制的数值可以区分消失的两个数字，记为low

 3.通过low，来将所给数组与包含1至N的数组中所有的数分为两类，分别是与low进行位运算后为为1，另一类则为0。然后将分类后的元素进行异或操作后，就可以从两类元素中分别得到消失的两个数字，进行返回即可。

1.3 具体代码

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int sum=0,n=nums.size()+2,x=0,y=0;
        vector<int> ret;
        //消失的两个数字异或
        for(int i=1;i<=n;i++) sum^=i;
        for(auto e:nums) sum^=e;
        //求出最低位为1
        int low=sum&(-sum);
        //根据最低位进行分组
        for(int i=1;i<=n;i++)
        {
            if(i&low)   x^=i;
            else        y^=i;
        }
        for(auto e:nums)
        {
            if(e&low)   x^=e;
            else        y^=e;
        }
        return {x,y};
    }
};

三、结语

        到此为止，本文有关位运算的讲解就全部到此结束了，如有不足之处，欢迎小伙伴们指出呀！

         关注我 _麦麦_分享更多干货：_麦麦_-CSDN博客

         大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！

        欢迎大家参观我的算法专栏：

麦麦的算法专栏https://blog.csdn.net/m0_73953114/category_12866812.html