287.寻找重复数

https://leetcode-cn.com/problems/find-the-duplicate-number/

解法一：二分

参照官方题解的解法一 cntp[i]表示nums中小于等于i的数有多少个，设重复数为target，则[1,target-1]中所有数满足cnt[i]<=i，[target,n]中所有数满足cnt[i] > i。 二分，每次比较cnt[mid]与mid的关系，判断应该在mid左侧还是右侧继续

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        l = 1
        r = n-1

        while l <= r :
            mid = l + (r-l) //2
            cnt = 0
            for i in range(n):  #求cnt[mid]
                if nums[i] <= mid:
                    cnt += 1
            if cnt > mid:
                r = mid - 1
            else:
                l = mid + 1
        return l