268. 丟失的數字

思路

因為亦或操作會將相同的數值對消，所以只要將「所有元素」與「缺一個數後的所有元素」做亦或，缺失的多出來的數字就會被剩下來。

• $[1, 2, 3, 4, 5, 6, 8, 9, 10]$，缺失7
• $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$，完整。

將兩個陣列做亦或，相同的數字都被對消，剩下缺失的數字7。

程式碼

位運算

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

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$