【leetcode】12. 数组-0～n-1中缺失的数字

题目

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

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

1 <= 数组长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

分析

从本题题意可以提出如下几个关键信息：

1. 数组长度为n-1
2. 每个数字都在范围0～n-1之内(一个n个元素)
3. 数组是递增有序，且唯一

跟进上面提取出的题意，可以得到信息：

1. 如果不缺数字的话，数字i = nums[i]
2. 当i位置的元素不是i,即i != nums[i]的时候，则有j > i; nums[j] > j 且k < i; nums[k] == k

本题依旧是二分查找问题，只是调整范围的判断条件有所调整。

时间复杂度：O(logN)
空间复杂度：O(1)

代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};