【程序员面试金典】面试题 17.19. 消失的两个数字-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 17.19. 消失的两个数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

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

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

示例 1:

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

示例 2:

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

提示：

nums.length <= 30000

解题思路

思路：最直观的想法是，位运算。消失的两个数字和只出现一次的两个元素，本质上是一样的。此处，先求出数组中元素的异或结果，然后再求出所有元素的异或结果，这样就得到消失的两个数字的异或结果。现在问题转换为如何将这两个数字分开，可以使用位运算求出这两个数字低位第一个不同的位置k，即异或结果中低位第一个出现的1，然后再根据数组中元素与所有元素中的每一个元素的k位置是1还是0将这两组元素分开即可。

vector<int> missingTwo(vector<int>& nums) 
{
   int n=nums.size();
   //xo得到的结果是消失的两个数字 0^a=a
   int xo=0;
   for(int i=1;i<=n+2;i++)
     xo^=i;
   for(int i=0;i<n;i++)
     xo^=nums[i];
   //现在需要将这两个数字分开
   int k=1;
   //直到找到xo为1的那一位 即两数第一个不同的那一位
   while((k&xo)==0)
     k<<=1;
   //将k位为1的分到res1
   int res1=0;
   //将k位为0的分到res2
   int res2=0;
   for(int i=1;i<=n+2;i++)
   {
      if(k&i)
        res1^=i;
      else
        res2^=i;
   }
   for(int i=0;i<n;i++)
   {
      if(k&nums[i])
        res1^=nums[i];
      else
        res2^=nums[i];
   }
   return {res1,res2};
}

总结：0^a=a，注意这一点，即异或结果的初始化为0。

vector<int> missingTwo(vector<int>& nums) 
{
   int n=nums.size();
   //xo得到的结果是消失的两个数字 0^a=a
   int xo=0;
   for(int i=1;i<=n+2;i++)
     xo^=i;
   for(int i=0;i<n;i++)
     xo^=nums[i];
   //现在需要将这两个数字分开
   int k=xo&(-xo);
   //将k位为1的分到res1
   int res1=0;
   //将k位为0的分到res2
   int res2=0;
   for(int i=1;i<=n+2;i++)
   {
      if(k&i)
        res1^=i;
      else
        res2^=i;
   }
   for(int i=0;i<n;i++)
   {
      if(k&nums[i])
        res1^=nums[i];
      else
        res2^=nums[i];
   }
   return {res1,res2};
}

总结：可以使用xo&(-xo)得到xo低位的第一个1，因为负数是以补码的形式存储的，即-xo=~xo+1，比如xo=1100，那么~xo=0011，-xo=0100。文章来源地址https://www.toymoban.com/news/detail-517746.html

到了这里，关于【程序员面试金典】面试题 17.19. 消失的两个数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！