面試題 17.19. 消失的兩個數字

面試題 17.19. 消失的兩個數字

? 給定一個數組，包含從 1 到 N 所有的整數，但其中缺了兩個數字。你能在 O(N) 時間內只用 O(1) 的空間找到它們嗎？

? 以任意順序返回這兩個數字均可。

示例 1:

輸入: [1]
輸出: [2,3]

示例 2:

輸入: [2,3]
輸出: [1,4]

提示：

• nums.length <= 30000

---

解題思路

? 這道題其實就是 268. 丟失的數字 和 137. 只出現一次的數字 II 的一個組和題，只要這兩道題會了，然后稍微變化一下就變成了這道題！無非就是這道題出現一次的數字是兩個，而我們得像 268. 丟失的數字 這道題一樣去遍歷所有的整數兩次，換在 137. 只出現一次的數字 II 這道題上無非就是其它數字出現了兩次！

? 也就是說，這道題轉化為了：一個數組中從 [1, n] 的數字只有兩個數字出現了一次，而其它數字出現了兩次！這個轉化很關鍵！

1. 首先，我們用一個變量 n，去遍歷【異或上】 nums 數組中的每一個元素，然后再去遍歷【異或上】 [1, nums.size() + 2] 區間內所有的數字，最后顯而易見，那些出現了兩次的數字，在兩次的遍歷之后都被抵消了，所以最后得到的 n 就是兩個只出現一次的元素的異或體，假設這兩個出現一次的元素分別是 a 和 b，那么 n = a ^ b。
2. 接著，我們考慮一個性質：因為 a 和 b 一定是不同的，所以 n 的比特位中一定會存在某些位為 1（因為異或之后，相異的比特位得到的就是 1），而這些比特位對于 a 和 b 來說，不是 a = 1，b = 0，就是 a = 0，b = 1，那么我們只需要根據找到 n 中比特位為 1 的其中一個位置 pos（代碼中我們是找最右側的那個），然后再到 nums 數組中遍歷一遍，根據每個數字的 pos 處比特位的值進行劃分，這里規定 pos 處比特位為 1 的劃分存在 a 的集合 seta 中，而為 0 的劃分在存在 b 的集合 setb 中，最后得到的就是一個不含有 a 的異或集合，一個不含有 b 的異或集合！
3. 此時 問題就轉化為了分別求 seta 和 setb 中在 [0, nums.size() + 2] 上消失的那個數字，那不就很簡單了嗎，我們只需要讓 seta 和 setb （此時這兩個集合存放的是 nums 中出現一次的數字）分別去遍歷一次 [1, nums.size() + 2] 上所有數字，最后出現一次的那些數字因為遍歷第二遍后都被抵消了，而那個消失的數字就會在最后的異或結果被得到，兩個集合都是如此！

? 解析有點繞，建議畫圖跟著分析，代碼如下所示：

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {// 1. 假設丟失的是a和b，那么先異或上全部元素，得到的結果就是a^bint n = 0;for(int i = 0; i < nums.size(); ++i)n ^= nums[i];for(int i = 1; i <= nums.size() + 2; ++i)n ^= i;// 2. 找到a和b比特位中為1的其中一個位置（a和b是不同的，所以一定存在這個比特位為1）int pos = 0;while(true){if((n >> pos) & 1)break;pos++;}// 3. 根據這個相異的比特位就能劃分成兩個集合seta和setbint seta = 0, setb = 0;for(int i = 0; i < nums.size(); ++i){if((nums[i] >> pos) & 1)seta ^= nums[i];elsesetb ^= nums[i];}// 4. 此時就是分別在seta和setb中找只存在一次的數，也就是a和b，那么只需要再遍歷異或一遍所有整數即可for(int i = 1; i <= nums.size() + 2; ++i){if((i >> pos) & 1)seta ^= i;elsesetb ^= i;}return { seta, setb };}
};