题目链接
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; } };
参考资料
[1]
LeetCode 面试题 17.19. 消失的两个数字: https://leetcode-cn.com/problems/missing-two-lcci/
[2]
LeetCode 面试题56 - I. 数组中数字出现的次数: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
[3]
LeetCode 136. 只出现一次的数字: https://leetcode-cn.com/problems/single-number/
[4]
LeetCode 137. 只出现一次的数字 II: https://leetcode-cn.com/problems/single-number-ii/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
