程序员面试金典 - 面试题 17.19. 消失的两个数字（数学/位运算）

1. 题目

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。

你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

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

示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
nums.length <= 30000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-two-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 数学公式

$1^2+2^2+3^2+4^2+....+n^2=n\ast (n+1)\ast (2n+1)/6$
$1+2+...+n=n\ast (1+n)/2$

class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int n = nums.size()+2, a, b;
long sum = 0, squareSum = 0;
for(int i = 0; i < nums.size(); ++i)
{
sum += nums[i];
squareSum += nums[i]*nums[i];
}
squareSum = long(n)*(n+1)*(2*n+1)/6 - squareSum;
sum = n*(n+1)/2 - sum;
for(a = 1; a <= n; ++a)
{
if(2*a*(sum-a) == sum*sum - squareSum)
break;
}
b = sum-a;
return {a,b};
}
};

72 ms 22.5 MB

2.2 常规解法

class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> ans;
int i, j;
for(i = 1, j = 0; i <= nums.size()+2 && j < nums.size(); ++i)
{
if(nums[j] != i)
ans.push_back(i);
else
j++;
if(ans.size()==2)
return ans;
}
if(ans.size()==1)
ans.push_back(i);
else if(ans.size()==0)
{
ans.push_back(i);
ans.push_back(i+1);
}
return ans;
}
};

116 ms 22.4 MB

2.3 位运算

• 0 异或所有数，以及1-n的所有数，只出现1次的两个数的异或值得到了
• 把上面异或值不为0的二进制位找到
• 用这个位把 1到n 和数组里的数（2n-2 个），按照上面找出的二进制位，分成2组
• 即得到出现1次的两个数

class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int XOR = 0, a = 0, b = 0, i;
for(auto& n : nums) XOR ^= n;
for(i = 1; i <= nums.size()+2; ++i) XOR ^= i;
for(i = 0; i < 32; ++i)
if(XOR&(1<<i))//a、b二进制不同的位
break;// i为 a,b 不相同的二进制位
for(auto& n : nums)
{
if((n>>i)&1)//分组
a ^= n;
else
b ^= n;
}
for(int j = 1; j <= nums.size()+2; ++j)
{
if((j>>i)&1)
a ^= j;
else
b ^= j;
}
return {a,b};
}
};

80 ms 22.3 MB

最后

以上就是怡然酸奶为你收集整理的程序员面试金典 - 面试题 17.19. 消失的两个数字（数学/位运算）的全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 17.19. 消失的两个数字（数学/位运算）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。