题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

/*
         2 3     
苹果 ：  2 3 4 5 6 7
抽屉 : 1 2 3 4 5 6 7
每次对抽屉进行二分,目标是找数的个数大于抽屉个数的一边
*/
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 对抽屉进行二分
        int l = 1 , r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            int s = 0;
            // 统计一下[1,mid]区间苹果数量
            for(int x : nums){
                if(x >= l && x <= mid ) 
                    s++;
            }
            if(s > mid - l + 1) // 目标在左区间
                r = mid;
            else
                l = mid + 1;

        }
        return r;
    }
};

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla