题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

样例

算法：二分

首先因为数组长度为n+1，数字只有1到n，根据抽屉原理，则只有至少有一个数字重复！
可以根据二分：
（1）首先找到l到r的中间数mid；
（2）然后统计数组中小于mid的个数，若个数大于mid - l + 1,则说明要求的数在l到mid这一侧；否则就在mid+1到r这一侧。

时间复杂度：O(n*logn)

C++ 代码

class Solution {
public:

    //二分，时间为O(n*logn)
    int findDuplicate(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size() -1;
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >>1;
            int res = 0;
            for(auto x : nums)
            {
                if(x >= l && x <= mid) res++; 
            }

            if(res > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};