题目描述

1. 0到n-1中缺失的数字

样例

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

输出：3

算法1

(暴力枚举) $O(n)$

分析数据：数据是0～n的整数，且递增，对于n个的数据，增长方式是类似 0,1,2....

如果数组的长度时0，直接返回0
如果数组的长度是1， 里面的数可能是0，也可能是1， 直接返回1-nums[0]
如果数组的长度大于2，可以将当前位置的值和下一个位置的值进行比较

时间复杂度分析：最多循环完数组

C++ 代码

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

    }
};