初识算法 · 位运算(end)
目录
前言：
本文作为初识算法 · 位运算的最后一篇文章，使用一道hard题目来结束这个专题，题目的链接为：
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
还是和前文一样，通过三个部分介绍，题目解析，算法原理，算法编写来介绍。
那么话不多说，进入主题吧！
题目解析
题目的要求十分简单，是让我们在一段连续数字区间里面找到缺失两个数字，数字的区间是从1到N的。要求非常简单。
所以我们直接进入到算法原理部分。
算法原理
这道题目其实是丢失的数字和只出现一次的数字III的结合，链接为：
260. 只出现一次的数字 III - 力扣（LeetCode）
结合两道题目的描述，我们就直到就是这两个结合起来嘛，所以使用异或运算律，将数集分为两组是肯定的，可是这里一共只有一段区间，我们去哪里找呢？简单，我们自己创一个区间不就行了吗？
因为这道题目可以分析为，在一堆数字里面，只有两个数字出现了一次，其他数字出现了两次。
所以使用异或，将其他数字全部干掉的同时，使用异或运算，将数分组，所以a和在某个比特位上同组的数字异或，b同理，最后的结果就是我们的答案。
这道题可以使用ret & -ret，也可以直接while找，都是可以的。
算法编写
class Solution
{
public:
vector<int> missingTwo(vector<int>& nums)
{
//两堆数字异或
int tmp = 0;
for(auto e : nums) tmp ^= e;
for(int i = 0;i <= nums.size() + 2; i++) tmp ^= i;
//找出不同
int diff = 0;
while(1)
{
if(((tmp >> diff) & 1) == 1) break;
else diff++;
}
//开始分组
int a = 0, b = 0;
for(int x : nums)
if(((x >> diff) & 1) == 1) a ^= x;
else b ^= x;
for(int i = 0; i <= nums.size() + 2; i++)
if(((i >> diff) & 1) == 1) a ^= i;
else b ^= i;
return { a, b };
}
};感谢阅读！
原文地址：https://blog.csdn.net/2301_79697943/article/details/143808760
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！