【位运算】丢失的数字（easy）

题⽬链接： 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)。