【剑指 offer】0到n - 1缺失的数字（可以二分）

1、题目描述

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

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

样例

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

2、问题描述：

3、问题关键：

• 可以二分法。
• 直接查找。nums[i] =?i
• 差值。n * (n + 1) / 2 - sum;

4、C++代码：

方法1：

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

方法2:

class Solution {//直接查找。
public:
    int getMissingNumber(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++) {
            if (nums[i] != i) return i;
        }
        return nums.size(); 
    }
};

算法3:

class Solution {//差值的方法。
public: 
    int getMissingNumber(vector<int> & nums) {
        int sum = 0; 
        int n = nums.size();
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        int res = n *(n + 1)/2 - sum;
        return res;
    }
};