要求不能改变原数组。否则可以直接排序后查找。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {

        int left = 1;
        int right = nums.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            int cnt = 0;
            for (int i = 0; i < nums.size(); ++i)
            {
                if (nums[i] <= mid) ++cnt;
            }
                
            if (cnt > mid) right = mid - 1;
            else left = mid + 1; 
        }
        return left;
    }
};