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

很简练，时间复杂度还有提高空间

边界情况过不去，比如输入【0】

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

改成这个可以ac

你这个有点小问题，如果i = nums.size()的时候，就会越界了

?return nums.size()不是可以

不会吧，肯定有答案吧，所以写while也没事吧

改成$i<=nums.size()$即可

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int cnt = 0;
        for(int x : nums)
        {
            if(x == cnt) cnt++;
        }
        return cnt;
    }
};

强~~~

6

想不到，太巧妙了

加油hh

有一个办法似乎能避免$n$缺失，就是初始的时候$r=nums.size()$，不要$-1$，这样如果都没有$l$就会变成$r$，返回$r$的时候就是$n$

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

感觉所有数都满足nums[i] == i 这种特殊情况放在while循环前面判断比较好，这样确保循环是有意义的；

放到前面去确实会好一些hh

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int sum = 0;
        for (int i: nums) sum += i;
        return (1 + nums.size()) * nums.size() / 2 - sum;
    }
};

class Solution {
public:
int getMissingNumber(vector[HTML_REMOVED]& nums) {
if(nums.empty())
return 0;
int ans;
int i;
int sum=0;
for (i=0;i<nums.size();i++)
{
sum+=nums[i];
}
int n=nums.size();
int total=n*(n+1)/2;
ans=total-sum;
return ans;
}
};

class Solution {
public:
int getMissingNumber(vector[HTML_REMOVED]& nums) {
int i = 0;
for(int x : nums){
if(x != i) break;
else i++;
}
return i;
}
};
这个是不是简单点

n很大的话容易tle

彩

为啥这个题二分的执行时间还不如直接遍历

因为存在缺失的数字就是第一个的情况，直接遍历O(1)就出了，而二分得log(n).

数据很大的时候二分还是很好的

if (nums[r] == r) r ++ ;为什么r要++啊？

懂了，特判缺失是n的情况

这个时间复杂度是怎么分析的？有大佬教教吗？

如果一开始r设定为nums.size()就不需要特判了

auto a=nums.begin();
int i;
for( i=0;i<nums.size();i++)
{
if(nums[i]!=i) break;
}
return i;

自己推了一遍 思路Tql

y总，题目中说的是长度为 n−1 的递增排序数组，所以数组下标 应该是到n-2,数组中的值到n-1

首先求出最后一个节点是多少（设它为n)在求出从1加到n的值（设为b），然后求出输入值的和（设为c），输出b - c

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

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

};

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int n=0;
        for(int x:nums)
        {
            if(n!=x)
            break;
            n++;
        }
        return n;
    }
};

😆

👍

%

如果取值很大的话，容易TLE

写成了r=mid-1，结果错了

强

y总写的真好！！！！yyds！！
但对于还没学算法的我来说还是有点困难
如果你也是，可以看一看我这个调了半天（30-60min）的程序

https://www.acwing.com/solution/content/54429/