【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法-阿里云开发者社区

【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法

2022-06-25 88

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 面试题 17.19. 消失的两个数字

题目链接

LeetCode 面试题 17.19. 消失的两个数字^[1]

题目描述

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

示例1

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

示例2

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

提示：

题解

位运算

是不是很熟悉？这其实就是 LeetCode 另一道位运算题目：

LeetCode 面试题56 - I. 数组中数字出现的次数^[2]

LeetCode 136. 只出现一次的数字^[3]

LeetCode 137. 只出现一次的数字 II^[4]

这题就与本题无关了，我们留着下次继续讲。

数学法

下标哈希

代码

位运算（c++）

classSolution {
public: 
vector<int>missingTwo(vector<int>&nums) {  
intn=nums.size();   
intx=0;    
for (autoi : nums) x^=i;  
for (inti=1; i<=n+2; ++i) x^=i;  
intlb=x&-x;   
inty=0;   
for (autoi : nums) {     
if (i&lb) y^=i;      
        }     
for (inti=1; i<=n+2; ++i) {  
if (i&lb) y^=i; 
        }   
return {y, y^x}; 
    }
};

数学法（c++）

classSolution {
public:
vector<int>missingTwo(vector<int>&nums) {  
longn=nums.size()+2;  
longS1=accumulate(nums.begin(), nums.end(), 0);  
longS2=0;  
for (autox : nums) S2+=x*x;   
longa=n*(n+1)/2-S1;     
longb=n*(n+1)*(2*n+1)/6-S2;    
longx= (a+sqrt(2*b-a*a))/2;   
longy= (a-sqrt(2*b-a*a))/2;     
return {x, y};
    }
};

下标哈希（c++）

classSolution {
public:  
vector<int>missingTwo(vector<int>&nums) { 
for (inti=0; i<3; ++i) {   
nums.push_back(-1);     
        }    
intn=nums.size();    
for (inti=0; i<n; ++i) {   
while (nums[i] !=-1&&i!=nums[i]) {  
swap(nums[i], nums[nums[i]]);    
            }        
        }     
vector<int>res;    
for (inti=1; i<n; ++i) {   
if (nums[i] ==-1) res.push_back(i);  
if (res.size() ==2) break;    
        }     
returnres;   
    }
};