0～n-1中缺失的数字(简单难度)

目录

题目概述(简单难度)

思路与代码

思路展现

方法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)