题目描述

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

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

样例

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

输出：3

算法1

(模拟，等差数列求和) $O(n)$

1. 首先用等差数列求和公式计算出 $0 \sim n - 1$ 的和 res
2. 遍历数组，每次 res 的值减去当前数 x
3. 最后 res 中剩下的就是 $0 \sim n - 1$ 中缺失的数字

时间复杂度

等差数列求和是 $O(1)$ 的，遍历数组的时间为 $O(n)$，所以总的时间复杂度为 $O(n)$。

C++ 代码

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

算法2

(二分) $O(logn)$

题目已知 nums 是长度为 $n - 1$ 的递增有序数组，所有数在 $0 \sim n - 1$ 范围内且每个数唯一
现在要找出 $0 \sim n - 1$ 中缺失的数字，观察值和下标的特点可以将区间划分成两部分，一部分值和下标相等， 另一部分值和下标不等，且缺失的数字就是数组中第一个值和下标不相等的那个下标，根据这个性质，就可以用二分二分出这个位置。

特殊情况：如果二分没有得到答案，说明缺失的数字是最后一个数 $n - 1$

1. 二分初始区间，l = 0, r = nums.size() - 1, mid = l + r >> 1
2. 二分的条件 nums[mid] != mid，如果成立更新区间 r = mid，否则 l = mid + 1
3. 二分结束 l = r 如果最后一个数的下标和值相等 r == nums[r]，说明缺失的就是最后一个数 $n - 1 / r + 1$

时间复杂度

二分中的迭代只会执行 $logn$ 次，所以时间复杂度为 $O(logn)$

C++ 代码

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty()) return 0;

        int n = nums.size() - 1;
        int l = 0, r = n;

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

        if (r == nums[r]) r ++ ;

        return r;
    }
};