脚撕LeetCode(剑指Offer53)Easy

题目地址：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例 1: 输入: [0,1,3] 输出: 2 示例2: 输入: [0,1,2,3,4,5,6,7,9] 输出: 8 限制： 1 <= 数组长度 <= 10000

这道题的思路就是，给你一个数组，数组长度是n-1，数字包括0～n-1等n位数，返回缺失的数字

一、爆破法

爆破法的思路很简单，循环叠加i，如果i不等于nums[i]就说明缺失，如果最后执行完了都没有返回，说明缺失的是n-1；

执行结果如下：

122 / 122 个通过测试用例

状态：通过

执行用时: 0 ms

内存消耗: 38.9 MB

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

二、二分法

二分法的思路就是，二分查找，

如果左边缺失，那么(0 + length -1) /2的值必然大于nums[(0 + length -1)]，

如果右边缺失，则必然是等于（因为缺失的也就是相当于右边大1，那么1/2 =0，所以m和nums[m]肯定对不上)，当等于的时候左边指针右移（二分法的右移），当不等于的时候，则右指针左移；

执行结果如下：

122 / 122 个通过测试用例

状态：通过

执行用时: 0 ms

内存消耗: 38.8 MB

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

思路都很简单，但是没有找到内存很低的方法。。。。。果然越简单的题目越难满分