题目描述

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int L=1,R=nums.size()-1;//因为所有数字均在1-n内，所以左边界是1
        while(L<R){
           int mid=L+(R-L)/2;
           int s=0;
           for(auto x:nums){
               if(x>=L && x<=mid){//每次只迭代一边数字数量
                   s++;
               }
            }
            if(s>mid-L+1) R=mid;//如果左边数数量大于右边，选择左边区间，让范围R=mid
            else L=mid+1;//如果左边数数量小于右边，选择右边区间，让范围L=mid+1

        //   for(auto x:nums) s+=x >= 1 && x<= mid;//s为统计数的个数
        //   for(auto x:nums)迭代容器中的所有值
        //   if(s>mid-L+1) R=mid;
        //   else L=mid+1;
        }
        return R;



    }
};

不知道为什么R=nums.size()-1

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size() - 1;
        int l = 1, r = n;
        while (l < r){
            int mid = l + r >> 1;
            int cnt = 0;
            for (auto x : nums)//迭代容器中的所有值
                if (x >= l && x <= mid)
                    cnt++;
            if (cnt > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla