濮阳网站建设陈帅,在线手机网站建设,在线app开发网站建设,微信小程序制作教程视频1. 题目
给定一个数组#xff0c;包含从 1 到 N 所有的整数#xff0c;但其中缺了两个数字。
你能在 O(N) 时间内只用 O(1) 的空间找到它们吗#xff1f;
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]示例 2:
输入: [2,3]
输出: [1,4]提示#xff1a…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 数学公式
12223242....n2n∗(n1)∗(2n1)/61^22^23^24^2....n^2 n*(n1)*(2n1)/612223242....n2n∗(n1)∗(2n1)/6 12...nn∗(1n)/212...n n*(1n)/212...nn∗(1n)/2
class Solution {
public:vectorint missingTwo(vectorint 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)*(n1)*(2*n1)/6 - squareSum;sum n*(n1)/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:vectorint missingTwo(vectorint nums) {sort(nums.begin(), nums.end());vectorint 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);elsej;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(i1);}return ans;}
};116 ms 22.4 MB
2.3 位运算
0 异或所有数以及1-n的所有数只出现1次的两个数的异或值得到了把上面异或值不为0的二进制位找到用这个位把 1到n 和数组里的数2n-2 个按照上面找出的二进制位分成2组即得到出现1次的两个数
class Solution {
public:vectorint missingTwo(vectorint 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(1i))//a、b二进制不同的位break;// i为 a,b 不相同的二进制位for(auto n : nums){if((ni)1)//分组a ^ n;elseb ^ n;}for(int j 1; j nums.size()2; j){if((ji)1)a ^ j;elseb ^ j;}return {a,b};}
};80 ms 22.3 MB
