剑指offer 56- 0到n-1中缺失的数字

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

在范围 0到 n−1 的 n个数字中有且只有一个数字不在该数组中，请找出这个数字。

样例

输入：[0,1,2,4]

输出：3

分析：
算法一：数学推导

假设缺失值是x，则

最终结果：

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(auto x:nums) sum += x;
        return (n*(n+1)/2 - sum);
    }
};

算法二：使用二分

观察数据的特点：具有二段性
即黄色部分满足：

红色部分：：
还有一种特殊情况是所有的 此时缺失的值就是最后一个数据，即n
时间复杂度：

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty()) return 0; 
        int l=0, r = nums.size()-1;
        // if (nums[r] == r) r ++ ;
        if(nums.back() != r+1) return r+1; //特判：缺失的是最后一个

        while(l<r) {
            int mid = l+r >> 1;
            if(nums[mid] != mid) r = mid;
            else l= mid+1;
        }
        return r;
    }
};