算法1

(二分查找)

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

算法2

(暴力破解)

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