题目描述

blablabla

样例

blablabla

算法1

(二分) $O(logn)$

直接在数组的后面补一个数，然后保证数组为升序，找到最靠近左边的大于位置的值返回就可以了。

C++ 代码

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

算法2

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

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla