一. 题目

二. 思路

1. 二分

三. 代码

1. 二分

class Solution
{
    static final int N = (int) 1e5 + 10;

    int tfind(int[] nums, int l, int r, int n)
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i)
                cnt += (nums[i] <= mid ? 1 : 0);
            if (cnt <= mid) l = mid + 1;
            else r = mid;
        }

        return l;
    }

    public int findDuplicate(int[] nums)
    {
        return tfind(nums, 1, nums.length, nums.length);
    }
}