#268. Missing Number

題目描述

給你一個長度[0, n]且含有n個唯一數字的陣列nums，回傳範圍中唯一一個消失的數字。

限制條件

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
每個數字都是唯一的。

解題思路

Sorting

最直覺的方式就是用Sorting先整理陣列，然後根據陣列的位置比對數字找出消失的那個數字。因為數字會是[0, n]之間，而陣列長度只會檢查到[0, n-1]，所以如果迴圈檢查完仍然沒有找到消失的數字，那麼答案就會是最後一個數字。

public class Solution {
    public int MissingNumber(int[] nums) {
        Array.Sort(nums);
        for(int i=0;i<nums.Length;i++){
            if(i!=nums[i]) return i;
        }
        return nums.Length;
    }
}

複雜度分析：

時間複雜度：最差的情況會檢查完所有數字，同時Sort()會花掉n * log n的時間，時間複雜度為O(n * log n)。
空間複雜度：空間複雜度為O(1)。

Follow-up

你可以實作出空間複雜度O(1)以及時間複雜度O(n)的解法嗎？

XOR

上一個解法使用了Sort()因此時間複雜度是O(n * log n)，但是空間複雜度是O(1)，為了讓時間複雜度降至O(n)，則不能使用Sort()。

在這種限制下則可以使用XOR來解決問題。

互斥或(XOR)運算子的邏輯如下：

＼	0	1
0	False	True
1	True	False

使用互斥或(XOR)運算時，兩個相同的數字，互斥邏輯成立，所以會變成0。而0與其他數字互斥或(XOR)運算時，或(OR)的邏輯成立，因此會得出的其他數字。

由於陣列位置和位置上的數字除了不見的數字以外，都會是成對的，所以可以用XOR來消除，而剩下的那個就會是不見的數字。記得消失的數字有可能會等於陣列長度，而在迴圈中只會處理到n-1個數字，所以最後也要和陣列長度比對一次，才能檢查到所有數字。

public class Solution {
    public int MissingNumber(int[] nums) {
        int ans = 0;
        for(int i=0;i<nums.Length;i++){
            ans ^= i ;
            ans ^= nums[i];
        }
        return ans^nums.Length;
	}
}

複雜度分析：

時間複雜度：時間複雜度為O(n)。
空間複雜度：空間複雜度為O(1)。

學習重點

Sort
XOR