LeetCode刷题（82）～消失的两个数字【分组异或】

题目描述

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

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

示例 1:

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

  

 

  
1
  
2
 

示例 2:

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

  

 

  
1
  
2
 

提示：

• nums.length <= 30000

解答 By 海轰

提交代码

vector<int> missingTwo(vector<int>& nums) { nums.push_back(2); nums.push_back(2); for(int i=0;i<nums.size();++i) { int newindex=abs(nums[i])-1; nums[newindex]=nums[newindex]*(-1); } vector<int> res; for(int i=0;i<nums.size();++i) { if(nums[i]>0) res.push_back(i+1); } return res; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

运行结果

解答

Demo【思路】

vector<int> missingTwo(vector<int>& nums) { int sum=0; for(int num:nums) sum+=num; int sumoftwo=(1+nums.size()+2)*(nums.size()+2)/2-sum; int midnum=sumoftwo/2; sum=0; for(int num:nums) { if(num<=midnum) sum+=num; } vector<int> res; res.push_back((1+midnum)*midnum/2-sum); res.push_back(sumoftwo-res[0]); return res; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

Demo【分组异或 思路】

vector<int> missingTwo(vector<int>& nums) { int ans = 0, n = nums.size(); for (int i = 1; i <= n + 2; i ++) ans ^= i; for (auto x: nums) ans ^= x; int one = 0; int diff = ans & -ans; for (int i = 1; i <= n + 2; i ++) if (diff & i) one ^= i; // ? for (auto x: nums) if (diff & x) one ^= x; return {one, one ^ ans}; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-two-lcci
参考：https://leetcode-cn.com/problems/missing-two-lcci/solution/zhuan-zhi-xiao-shi-de-shu-de-san-chong-jie-fa-by-w/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108143931