# 287.寻找重复数

[https://leetcode-cn.com/problems/find-the-duplicate-number/](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左侧还是右侧继续

```python
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
```
