# 268 - Missing Number

題目

img

暴力法

最簡單的方法之一就是用一個 set 儲存 nums 裡面所有的數字，然後從 0 檢查到 n，看哪個數字不在 set 裡。之所以用 set 是因為搜尋某個數字在不在裡面的效率比 array 高很多。簡單的實作如下：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());

        int n = nums.size();
        for(int i = 0; i <= n; ++i) {
            if(s.count(i) == 0) {
                return i;
            }
        }

        return -1;
    }
};

雖然時間複雜度是 O(n)，但空間複雜度也是 O(n)，我們能否用 O(1) 的空間複雜度解決這題呢？

Sum 解法

這個 nums 有一個很重要的特性，就是裡面的數字落在 0 到 n 之間，也就是說，假設沒有 missing number，總和就應該是 1 + 2 + ... + n。所以我們可以先把 1 到 n 的總和算出來，然後減掉所有 nums 裡面的 element，剩下的數字就是 missing number 啦。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int target_sum = 0, n = nums.size();
        for(int i = 0; i <= n; ++i) {
            target_sum += i;
        }

        for(int idx = 0; idx < n; ++idx) {
            target_sum -= nums[idx];
        }

        return target_sum;
    }
};

這個解法就只用 O(1) 的空間複雜度，比剛剛的解法有效率。可惜，這個解法有個缺點，你能想得出來是什麼缺點嗎？

Bitwise XOR 解法

上一個解法的缺點是，如果 n 很大（例如 n 是 INT_MAX），那 sum 就會 overflow，要特別注意。所以我們可以用另一個 Bitwise XOR 解法，這個解法利用的概念是 x ^ x = 0。所以我們可以先把 1 到 n 的所有數字都 XOR 起來，然後再跟 nums 裡面所有的數字 XOR，剩下沒被消掉的數字就是 missing number。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = 0, n = nums.size();
        for(int i = 0; i <= n; ++i) {
            ans ^= i;
        }

        for(int idx = 0; idx < n; ++idx) {
            ans ^= nums[idx];
        }

        return ans;
    }
};