admin管理员组文章数量:1030679
【位运算】消失的两个数字
面试题 17.19. 消失的两个数字
面试题 17.19. 消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
代码语言：javascript代码运行次数：0运行复制输入: [1]
输出: [2,3]示例 2:
代码语言：javascript代码运行次数：0运行复制输入: [2,3]
输出: [1,4]提示：
nums.length <= 30000
解题思路
这道题其实就是 268. 丢失的数字 和 137. 只出现一次的数字 II 的一个组和题，只要这两道题会了，然后稍微变化一下就变成了这道题！无非就是这道题出现一次的数字是两个，而我们得像 268. 丢失的数字 这道题一样去遍历所有的整数两次，换在 137. 只出现一次的数字 II 这道题上无非就是其它数字出现了两次！
也就是说，这道题转化为了：一个数组中从 [1, n] 的数字只有两个数字出现了一次，而其它数字出现了两次！这个转化很关键！
- 首先，我们用一个变量
n，去遍历【异或上】nums数组中的每一个元素，然后再去遍历【异或上】[1, nums.size() + 2]区间内所有的数字，最后显而易见，那些出现了两次的数字，在两次的遍历之后都被抵消了，所以最后得到的n就是两个只出现一次的元素的异或体，假设这两个出现一次的元素分别是a和b，那么n = a ^ b。 - 接着，我们考虑一个性质：因为
a和b一定是不同的，所以n的比特位中一定会存在某些位为1（因为异或之后，相异的比特位得到的就是1），而这些比特位对于a和b来说，不是a = 1，b = 0，就是a = 0，b = 1，那么我们只需要根据找到n中比特位为1的其中一个位置pos（代码中我们是找最右侧的那个），然后再到nums数组中遍历一遍，根据每个数字的pos处比特位的值进行划分，这里规定pos处比特位为1的划分存在a的集合seta中，而为0的划分在存在b的集合setb中，最后得到的就是一个不含有a的异或集合，一个不含有b的异或集合！ - 此时 问题就转化为了分别求
seta和setb中在[0, nums.size() + 2]上消失的那个数字，那不就很简单了吗，我们只需要让seta和setb（此时这两个集合存放的是nums中出现一次的数字）分别去遍历一次[1, nums.size() + 2]上所有数字，最后出现一次的那些数字因为遍历第二遍后都被抵消了，而那个消失的数字就会在最后的异或结果被得到，两个集合都是如此！
解析有点绕，建议画图跟着分析，代码如下所示：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
// 1. 假设丢失的是a和b，那么先异或上全部元素，得到的结果就是a^b
int n = 0;
for(int i = 0; i < nums.size(); ++i)
n ^= nums[i];
for(int i = 1; i <= nums.size() + 2; ++i)
n ^= i;
// 2. 找到a和b比特位中为1的其中一个位置（a和b是不同的，所以一定存在这个比特位为1）
int pos = 0;
while(true)
{
if((n >> pos) & 1)
break;
pos++;
}
// 3. 根据这个相异的比特位就能划分成两个集合seta和setb
int seta = 0, setb = 0;
for(int i = 0; i < nums.size(); ++i)
{
if((nums[i] >> pos) & 1)
seta ^= nums[i];
else
setb ^= nums[i];
}
// 4. 此时就是分别在seta和setb中找只存在一次的数，也就是a和b，那么只需要再遍历异或一遍所有整数即可
for(int i = 1; i <= nums.size() + 2; ++i)
{
if((i >> pos) & 1)
seta ^= i;
else
setb ^= i;
}
return { seta, setb };
}
};【位运算】消失的两个数字
面试题 17.19. 消失的两个数字
面试题 17.19. 消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
代码语言：javascript代码运行次数：0运行复制输入: [1]
输出: [2,3]示例 2:
代码语言：javascript代码运行次数：0运行复制输入: [2,3]
输出: [1,4]提示：
nums.length <= 30000
解题思路
这道题其实就是 268. 丢失的数字 和 137. 只出现一次的数字 II 的一个组和题，只要这两道题会了，然后稍微变化一下就变成了这道题！无非就是这道题出现一次的数字是两个，而我们得像 268. 丢失的数字 这道题一样去遍历所有的整数两次，换在 137. 只出现一次的数字 II 这道题上无非就是其它数字出现了两次！
也就是说，这道题转化为了：一个数组中从 [1, n] 的数字只有两个数字出现了一次，而其它数字出现了两次！这个转化很关键！
- 首先，我们用一个变量
n，去遍历【异或上】nums数组中的每一个元素，然后再去遍历【异或上】[1, nums.size() + 2]区间内所有的数字，最后显而易见，那些出现了两次的数字，在两次的遍历之后都被抵消了，所以最后得到的n就是两个只出现一次的元素的异或体，假设这两个出现一次的元素分别是a和b，那么n = a ^ b。 - 接着，我们考虑一个性质：因为
a和b一定是不同的，所以n的比特位中一定会存在某些位为1（因为异或之后，相异的比特位得到的就是1），而这些比特位对于a和b来说，不是a = 1，b = 0，就是a = 0，b = 1，那么我们只需要根据找到n中比特位为1的其中一个位置pos（代码中我们是找最右侧的那个），然后再到nums数组中遍历一遍，根据每个数字的pos处比特位的值进行划分，这里规定pos处比特位为1的划分存在a的集合seta中，而为0的划分在存在b的集合setb中，最后得到的就是一个不含有a的异或集合，一个不含有b的异或集合！ - 此时 问题就转化为了分别求
seta和setb中在[0, nums.size() + 2]上消失的那个数字，那不就很简单了吗，我们只需要让seta和setb（此时这两个集合存放的是nums中出现一次的数字）分别去遍历一次[1, nums.size() + 2]上所有数字，最后出现一次的那些数字因为遍历第二遍后都被抵消了，而那个消失的数字就会在最后的异或结果被得到，两个集合都是如此！
解析有点绕，建议画图跟着分析，代码如下所示：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
// 1. 假设丢失的是a和b，那么先异或上全部元素，得到的结果就是a^b
int n = 0;
for(int i = 0; i < nums.size(); ++i)
n ^= nums[i];
for(int i = 1; i <= nums.size() + 2; ++i)
n ^= i;
// 2. 找到a和b比特位中为1的其中一个位置（a和b是不同的，所以一定存在这个比特位为1）
int pos = 0;
while(true)
{
if((n >> pos) & 1)
break;
pos++;
}
// 3. 根据这个相异的比特位就能划分成两个集合seta和setb
int seta = 0, setb = 0;
for(int i = 0; i < nums.size(); ++i)
{
if((nums[i] >> pos) & 1)
seta ^= nums[i];
else
setb ^= nums[i];
}
// 4. 此时就是分别在seta和setb中找只存在一次的数，也就是a和b，那么只需要再遍历异或一遍所有整数即可
for(int i = 1; i <= nums.size() + 2; ++i)
{
if((i >> pos) & 1)
seta ^= i;
else
setb ^= i;
}
return { seta, setb };
}
};本文标签： 位运算消失的两个数字
版权声明：本文标题：【位运算】消失的两个数字 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747675733a2202428.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论