剑指offer53-II(简单)：0~n-1中缺失的数字

题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

实例1：

1 2	输入: [0,1,3] 输出: 2

实例2：

1 2	输入: [0,1,2,3,4,5,6,7,9] 输出: 8

代码

方案1：暴力求解

缺失的数字分为两种情况：

第一种情况：缺失的是最后一个数字，即n-1，直接return nums.length。

第二种情况：缺失的是除最后一个数字之外的任何其他数字，这时它是数组中第一个元素值≠其对应的索引的数字。

class Solution {
    public int missingNumber(int[] nums) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i){
                return i;
            }
        }

        return nums.length;
    }
}

方案2：算法优化

采用二分法。

将数组分为两部分：左子数组和右子数组。

左子数组：元素值 = 索引

右子数组：首元素值 ≠ 索引

此时，缺失的数字即为右子数组的首元素。

class Solution {
    public int missingNumber(int[] nums) {
        //初始化
        int i=0,j=nums.length-1;

        //循环二分
        while(i<=j){
            int m=(i+j)/2;//默认向下取整

            if(nums[m]==m){
                i=m+1;
            }else {
                j=m-1;
            }
        }
        return i;//返回右子数组的首元素
    }
}

随笔

排序数组中的查找问题

首先想到用二分法来解决。

复杂度分析

方案1：

时间复杂度：O(n)，遍历为线性级复杂度。

空间复杂度：O(1)，几个变量使用常数大小的额外空间。

方案2：

时间复杂度：O(logn)，二分法为对数级复杂度。

空间复杂度：O(1)，几个变量使用常数大小的额外空间。

很显然，二分法更有优势。