题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    /*
    抽屉原理 
    把该放到抽屉0 1 2 4的这四个苹果放到0 ~ n-1这n个抽屉上，返回 没有苹果的抽屉号码
    */
    int getMissingNumber(vector<int>& nums) {
        int l = 0 , r = nums.size() ;
        while(l < r){
            int mid = l + r >> 1; // [l , mid][mid + 1 , r]
            int s = 0;
            for(auto x : nums){
                if(x >= l && x <= mid)
                    s++;
            }
            if(s < mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};