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 <= 104
- 0 <= nums[i] <= n
- nums 中的所有数字都 独一无二
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
题解
思路：排序 把nums数组排序 找出第一个下标和值不相等的返回索引 找不到，就返回数组长度
class Solution { public int missingNumber(int[] nums) { int i; Arrays.sort(nums); for(i=0;i<nums.length;i++){ if(nums[i]!=i){ break; } } return i; } }
思路：计数 新建一个ns数组用来存储对应nums是否缺失 所以ns比nums长1 ns的下标对应nums的元素 ns的值对应是否缺失（0是缺失，非0是不缺失）
class Solution { public int missingNumber(int[] nums) { int n=nums.length; int m=n+1; int[] ns=new int [m]; for(int i=0;i<n;i++){ ns[nums[i]]++; } int i; for(i=0;i<m;i++){ if(ns[i]==0){ break; } } return i; } }
官方
思路：位运算 因为两个相同的数异或等于0 一个数与0异或等于它自己 所以把数组nums增加[0,n]数 其中缺失的数只一个 其他数都是两个
class Solution { public int missingNumber(int[] nums) { int n=nums.length; int m=2*n+1; int[] ns=new int [m]; for(int i=0;i<m;i++){ if(i<n){ ns[i]=nums[i]; }else{ ns[i]=i-n; } } int miss=0; for(int i=0;i<m;i++){ miss^=ns[i]; } return miss; } }
官方
class Solution { public int missingNumber(int[] nums) { int xor = 0; int n = nums.length; for (int i = 0; i < n; i++) { xor ^= nums[i]; } for (int i = 0; i <= n; i++) { xor ^= i; } return xor; } }
思路：数学求和 [0,n]求和 和数组求和之差就是缺失的数
class Solution { public int missingNumber(int[] nums) { int n=nums.length; int sum=0; for(int i=0;i<n;i++){ sum+=nums[i]; } int total=(0+n)*(n+1)/2; return total-sum; } }
