1. 題目

給定一個(gè)數(shù)組，包含從 1 到 N 所有的整數(shù)，但其中缺了兩個(gè)數(shù)字。

你能在 O(N) 時(shí)間內(nèi)只用 O(1) 的空間找到它們嗎？

以任意順序返回這兩個(gè)數(shù)字均可。

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

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/missing-two-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 數(shù)學(xué)公式

$1^2+2^2+3^2+4^2+....+n^2=n?(n+1)?(2n+1)/6$
$1+2+...+n=n?(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 常規(guī)解法

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);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(i+1);}return ans;} };

116 ms 22.4 MB

2.3 位運(yùn)算

• 0 異或所有數(shù)，以及1-n的所有數(shù)，只出現(xiàn)1次的兩個(gè)數(shù)的異或值得到了
• 把上面異或值不為0的二進(jìn)制位找到
• 用這個(gè)位把 1到n 和數(shù)組里的數(shù)（2n-2 個(gè)），按照上面找出的二進(jìn)制位，分成2組
• 即得到出現(xiàn)1次的兩個(gè)數(shù)

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二進(jìn)制不同的位break;// i為 a,b 不相同的二進(jìn)制位for(auto& n : nums){if((n>>i)&1)//分組a ^= n;elseb ^= n;}for(int j = 1; j <= nums.size()+2; ++j){if((j>>i)&1)a ^= j;elseb ^= j;}return {a,b};} };

80 ms 22.3 MB

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 17.19. 消失的两个数字（数学/位运算）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。