leetcode-剑指offer 53

点击：题目链接：一个长度为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. 该数组是递增有序的
2. 数字只出现一次
3. 只有一个数不再数组内

因此首先我们想到的就是暴力的方法，逐一扫描找出该数

代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int tmp = 0;
        for(int i=0; i<nums.size(); i++){
            if(tmp != nums[i]) break;   //如果发现不同的就中断当前for循环
            tmp++;
        }
        return tmp;    //返回最终值
    }
};

思路二

根据暴力的解法，我们发现当低位出现数组下标和元素的值不匹配的时候，那么之后的所有的数都是不匹配的。因此我们可以使用二分法(双指针)。首先查看中值是否符合条件，若不相等右指针缩小范围。若相等，将左指针移动到中值，下一部分的二分之一。

代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=0, r=nums.size()-1;
        int mid;
        while(l <= r){
            mid = (l+r)/2;
            if(nums[mid] != mid)  r= mid-1;   //不等，右指针前挪，左指针不动
            else  l = mid+1;   //相等，左指针右挪，右指针不动
        }
        return l;
    }
};