【优选算法必刷100题】第038题（位运算）：消失的两个数字
🔥个人主页：Cx330🌸
❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》
《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔
🌟心向往之行必能至
🎥Cx330🌸的简介：
目录
前言：
聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力
位运算专题
38. 消失的两个数字
题目链接：
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题目描述：
题目示例：
算法原理（位运算）：
思路：
本题就是 268.丢失的数字+260.只出现一次的数字||| 组合起来的题。
先将数组中的数和【1，n+2】区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了 260.只出现了一次的数字||| 这道题
位运算解法代码（C++）：
代码一:位图
class Solution { public: vector<int> missingTwo(vector<int>& nums) { //将所有数异或在一起 int ret=0; for(auto x:nums) ret^=x; for(int i=1;i<=nums.size()+2;i++) ret^=i; //找出a，b比特位不同的那一位 int differ=0; while(1) { if(((ret>>differ)&1)==1) break; else differ++; } //根据differ位不同将所有数划分为两大类 int a=0,b=0; for(auto x:nums) if(((x>>differ)&1)==1) b^=x; else a^=x; for(int i=1;i<=nums.size()+2;i++) if(((i>>differ)&1)==1) b^=i; else a^=i; return {a,b}; } };代码二:异或
class Solution { public: vector<int> missingTwo(vector<int>& nums) { int temp=0; for(auto& x:nums) temp^=x; for(int i=1;i<=nums.size()+2;i++) temp^=i; //现在temp中剩下的是a^b，那么一定至少有一位是1，我们就提取最后一位 int ls=temp&(-temp); int a=0,b=0; for(auto&x:nums) { if(x&ls) a^=x; else b^=x; } for(int i=1;i<=nums.size()+2;i++) { if(i&ls) a^=i; else b^=i; } return {a,b}; } }; 
博主手记（字体还请见谅哈）：
总结:
结语:本文介绍了使用位运算解决"消失的两个数字"问题的两种方法。问题可转化为找出两个只出现一次的数字。方法一通过异或所有数后找出差异位，将数字分为两类分别异或；方法二利用异或结果的最低位1作为区分标准。两种方法都实现了O(n)时间复杂度和O(1)空间复杂度的解决方案，适用于处理大规模数据
