题目描述

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

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

样例

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

输出：3

这里给出4个解法

算法1

(二分)

1. 如果l是0，r是n - 1，那么就一定要判断边界条件if(A.empty()) return 0;
2. 最后也要判断if(A[r] == r) r ++，因为如果一直相等，l会一直右移，最后l = r = n - 1，如果这时候A[r] = r，说明确实的是n，所以让r ++。

时间复杂度

$O(logn)$

C++ 代码

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

        if(r == A[r]) r ++;
        return r;
    }
};

算法2

(二分)

1. 下面这种解法不用判断边界条件，可以AC，不知道是什么原因？知道的大佬麻烦给指点一下谢谢~
2. 和上面的不同就是r = n，而不是r = n - 1。

时间复杂度

$O(logn)$

C++ 代码

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

算法3

(模拟)

1. 将指针i定义在外面，判定[0]这种数据，最后跳出for()循环，i ++，所以缺失的是1。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int getMissingNumber(vector<int>& A) {
        int i = 0;
        for(i = 0; i < A.size(); i ++)
            if(i != A[i])
                return i;
        return i;
    }
};

算法4

(模拟)

1. 等差数列求和 - sum

时间复杂度

$O(n)$

C++ 代码

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

        return sum - s;
    }
};