题目描述

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

算法一

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty())return 0;
        for(auto i=nums.begin();i<nums.end()-1;i++){
            if(*i-*(i+1)!=-1)return (*i+*(i+1))/2;
        }
        if(nums[0]==0)return nums.size();
        return 0;
    }
};

算法2

二分法 $O(logn)$

通过不断缩小查找范围，找到缺少的数字

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty())return 0;
        int l=0,r=nums.size();
        if(nums[r-1]!=r)return r;
        while(l<r){
            int mid=l+r>>1;
            if(nums[mid]!=mid)r=mid;
            else l=mid+1;
        }
        return l;
    }
};