目录
题目概述(简单难度)
思路与代码
思路展现
方法1：二分法
代码示例
注意事项
方法2：位运算
代码示例
题目概述(简单难度)
题目链接:
思路与代码
思路展现
方法1：二分法
排序数组中的搜索问题，首先想到 二分法 解决。
这道题目使用二分法我是真没想到，这块我们直接上代码,看来还是本人题做的少了
代码示例
class Solution { public int missingNumber(int[] nums) { int i =0,j = nums.length - 1; while(i <= j) { int mid = (i+j)/2; if(nums[mid] == mid) { i= mid+1; }else { j = mid-1; } } return i; } }
注意事项
1：先来看核心思想
if(nums[mid] == mid) { i= mid+1; }else { j = mid-1; }
因为我们是一个长度为n-1的递增排序数组，并且每个数字都在范围0～n-1之内，这句话的意思等价于数组下标的值就等于我们在数组中所存储的值，例如：nums[0]=0,nums[1]=1…
那么当nums[mid] = mid的时候，就说明在我们中间下标再往前的数字都跟其下标的数字都一样，如果缺了我们 nums[mid] 是不可能等于 mid的，那么我们这个数组所缺少的数字就只能在我们mid下标之后了，所以能够每次处理就丢弃一半的数据， 每次降低1/2的规模，类似于一颗二叉树，查找次数为二叉树的高度, 因此复杂度降为 log2N --> O(logN)。所以让i=mid+1,相反，如果nums[mid] != mid,说明所少的数字就只能在我们mid下标之前了，此时就需要j = mid-1
2:
此时我们的while循环中i是一定要小于等于j的：
如果是小于j的话，此时会出现如下的测试用例跑不过的情况：
方法2：位运算
位运算的话首先需要记住以下的定律:
此时根据题目要求，如果数组不缺少数字的话，数组应该按照如下要求排列:
少了的数字该怎么办呢？我们直接来看代码是怎么解决的吧：
代码示例
class Solution { public int missingNumber(int[] nums) { int xor = 0; for (int i = 0; i < nums.length; i++){ xor ^= nums[i] ^ (i + 1); } return xor; } }
我们来分析一下代码为什么就可以找出来缺少的那个数字
首先如果是不缺少数字的话，例如0 ^ 0 ^ 1后为1，1 ^ 1 ^ 2 = 2,依次类推后到最后我们剩下的数字只有数组中最后一个数字.
而假如我们缺少数字的话，例如[0,1,2,3,4,5,6,7,9]中，我们可以发现是缺少8这个数字的，那么最后7 ^ 7 ^ 8 = 8,8 ^ 9 ^ 9 = 8,我们发现最后的数字就是我们所缺失的数字8，满足题意.
时间复杂度：O（N） 空间复杂度：O（1)
