题解 | #缺失数字#

题目解析： 我们可以从题目中提取出来几个关键点：

第一，抽取出来的数是从0开始到n的；
第二，选出的数字依然保持有序；
第三，缺失一个数。

那么，我们不妨先想想抽出来的数的可能性。
① 抽出来形如 [0,2,3,4,5] 的此类数，那么我们很容易知道就是1缺失，简单来说就是头尾完整，中间缺失。
② 抽出来形如 [1,2,3,4,5] 的此类数，那么很明显是0缺失，简单来说就是头缺失
③ 抽出来形如 [0,1,2,3,4] 的此类数，这一类情况是很容易遗忘的，因为看上去其实没什么问题，都是从0开始，然后到4结束，中间也没有缺失数字。虽然此类情况看上去不缺失，但是我们的题目因为明确说了缺失了一个数，那么这个数字必然就是比最后一个数字大一的那个数，也就是说缺失了5，这类情况我们叫为尾丢失。

到现在，其实题目就很简单了，我们只需要考虑上面的三种情况，不要漏掉形如上面三种的情况，那么AC这道题目就很简单了。但是题目还有一个另外的要求，时间复杂度要求在 $O(n)$ 或者 $O(logn)$ ，所以下面就分别给出这两种复杂度的解法。

方法一: 计数
计数，其实就是新建了一个数组，数组存储了对应下标值出现的次数，然后最后遍历这个数组，找到那个本该出现但是没有出现的数字。
图片说明
代码如下：

public int solve (int[] a) {
        // 算出数组的长度
        int n = a.length;
        // 计数数组的长度肯定是a数组中最大的那一个+1，如果a数组无序的情况下
        // 但是我们这道题目比较特殊，其实可以直接赋值n+1，我这里采用计数通用的初始化长度
        int[] nums = new int[a[n-1]+1];
        // 初始化计数数组
        for(int i = 0; i < n; i++){
            nums[a[i]]++;
        }
        // 遍历看哪个没有出现过的则返回
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0)
                return i;
        }
        // 出现了第三种情况，此时返回最后一个数+1 的那个数
        return a[n-1]+1;
    }

复杂度分析:
时间复杂度： $O(n)$ 。n为数组的长度，循环遍历了n次。
空间复杂度： $O(n)$ 。开辟了计数数组的空间。

方法二：对原来的数组进行一次遍历
方法一采用了计数的方式，其实这道题目我们还可以巧妙利用一个条件，就是取的数组保持了原来的有序性，那么也就是说a数组必然是从0开始的有序数组，所以我们只需要对其进行一次遍历，因为数组下标都是从0开始的，那么我们就只需要判断数组下标是否跟存储的值一致即可。
图片说明
代码如下:

public int solve (int[] a) {
        // 算出数组a的长度
        int n = a.length;
        // 得到此时出现的最大的数
        int end = a[n-1];
        // 因为题目已经保证了保持有序,所以下标值必须跟值一致
        for(int i = 0; i <= end; i++){
            // 当出现第一个下标与值不等的情况，则此时的下标就是缺失的数字
            if(i != a[i]){
                return i;
            }
        }
        // 到了这里证明数组a全部有序，而是缺失了比数组a中最大的大1的那个数
        return a[n-1]+1;
    }

复杂度分析:
时间复杂度： $O(n)$ 。n为数组的长度，循环遍历了n次。
空间复杂度： $O(1)$ 。没有开辟多余的空间。

方法三：二分
前面两种方法的时间复杂度都是 $O(n)$ ，但是题目给我们的要求是能不能用 $logn$ 来解决这道题目呢？
其实我们看到 $logn$ 这个时间复杂度，最容易想到的就是二分查找。其实主要还是利用下标与值相等这个条件，去维护左右边界，然后最终找到缺失的那个数字。
图片说明
代码如下：

public int solve (int[] a) {
        // 定义两个边界
        int l = 0,r = a.length-1;
        // 循环终止条件
        while(l <= r){
            // 取中点
            int m = (l+r)/2;
            // 当下标等于值的时候，左边界更新
            if(a[m] == m)
                l = m+1;
            // 否则，更新右边界
            else 
                r = m-1;
        }
        return l;
    }

复杂度分析:
时间复杂度： $O(logn)$ 。n为数组的长度。
空间复杂度： $O(1)$ 。没有开辟多余的空间。