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

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

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

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

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

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;
    }

复杂度分析:
时间复杂度:。n为数组的长度,循环遍历了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;
    }

复杂度分析:
时间复杂度:。n为数组的长度,循环遍历了n次。
空间复杂度:。没有开辟多余的空间。

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

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;
    }

复杂度分析:
时间复杂度:。n为数组的长度。
空间复杂度:。没有开辟多余的空间。