題?鏈接： 268. 丟失的數字

題?描述：

給定?個包含 [0, n] 中 n 個數的數組 nums ，找出 [0, n] 這個范圍內沒有出現在數組中的那個數。
?例 1：
輸?：nums = [3,0,1]
輸出：2
解釋：n = 3，因為有 3 個數字，所以所有的數字都在范圍 [0,3] 內。2 是丟失的數字，因為它沒
有出現在 nums 中。
?例 2：
輸?：nums = [0,1]
輸出：2
解釋：n = 2，因為有 2 個數字，所以所有的數字都在范圍 [0,2] 內。2 是丟失的數字，因為它沒
有出現在 nums 中。
?例 3：
輸?：nums = [9,6,4,2,3,5,7,0,1]
輸出：8
解釋：n = 9，因為有 9 個數字，所以所有的數字都在范圍 [0,9] 內。8 是丟失的數字，因為它沒
有出現在 nums 中。
?例 4：
輸?：nums = [0]
輸出：1
解釋：n = 1，因為有 1 個數字，所以所有的數字都在范圍 [0,1] 內。1 是丟失的數字，因為它沒有出現在 nums 中。
提?：
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
nums 中的所有數字都 獨???
進階：你能否實現線性時間復雜度、僅使?額外常數空間的算法解決此問題?

方法一：排序

一個簡單的做法是直接對 nums 進行排序，找到符合 nums[i] =i 的位置即是答案，如果不存在 nums[i]=i 的位置，則 n 為答案。

class Solution {public int missingNumber(int[] nums) {Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n; i++) {if (nums[i] != i) {return i;}}return n;}
}

復雜度分析
時間復雜度：O(nlogn)，其中 n 是數組 nums 的長度。排序的時間復雜度是 O(nlogn)，遍歷數組尋找丟失的數字的時間復雜度是 O(n)，因此總時間復雜度是 O(nlogn)。
空間復雜度：O(logn)，其中 n 是數組 nums 的長度。空間復雜度主要取決于排序的遞歸調用棧空間。

解法（位運算）：

算法思路：
異或
找缺失數、找出現一次數都是異或的經典應用。
我們可以先用 ret 對各個 nums[i] 進行異或，然后求得 [1,n] 的異或和 ans。
這樣最終得到的異或和表達式中，只有缺失元素出現次數為 1 次，其余元素均出現兩次（x⊕x=0），即最終答案 ans 為缺失元素。

C++ 算法代碼：

class Solution
{
public:int missingNumber(vector<int>& nums) {int ret = 0;for(auto x : nums) ret ^= x;for(int i = 0; i <= nums.size(); i++) ret ^= i;return ret;}
}

Java 算法代碼：

class Solution {public int missingNumber(int[] nums) {int ret = 0;for(int x : nums) ret ^= x;for(int i = 0; i <= nums.length; i++) ret ^= i;return ret;}
}

復雜度分析
時間復雜度：O(n)，其中 n 是數組 nums 的長度。需要對 2n+1 個數字計算按位異或的結果。
空間復雜度：O(1)。