C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, nums))
                r = mid;
            else
                l = mid + 1;
        }
        // 退出循环时check(l, nums)一定为true，因为check(n, nums)为true，所以不可能是全false的情形
        return l;
    }

private:
    // predicate(x): nums中<=x的个数超过x
    // 使得predicate(x)为true的最小x一定为重复数字，所以我们只需找F F F ... F [T] T ...T 第一个true的位置
    bool check(int x, vector<int>& nums) {
        int cnt = 0;
        for (auto t : nums) {
            if (t <= x) 
                ++cnt;
        }
        return (cnt > x);
    }
};