不修改数组找出重复的数字

二分模板1

(二分模板1) $O(nlogn)$

这道题不管是将区间划分为[l, mid], [mid + 1, r]
还是划分为[l, mid - 1], [mid, r]都可以的。

C++ 代码

class Solution {
public:
    bool go(int r, int mid, vector<int>& A)
    {
        int res = 0;
        for (auto x : A)
            if (x >= mid && x <= r)
                res ++;
        return res > r - mid + 1;
    }

    int duplicateInArray(vector<int>& A) {
        int n = A.size();
        int l = 1, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (go(r, mid, A)) l = mid;
            else r = mid - 1;
        }

        return l;
    }
};

模板2

C++ 代码

class Solution {
public:
    bool go(int l, int mid, vector<int>& A)
    {
        int res = 0;
        for (auto x : A)
            if (x >= l && x <= mid)
                res ++;
        return res > mid - l + 1;
    }

    int duplicateInArray(vector<int>& A) {
        int n = A.size();
        int l = 1, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (go(l, mid, A)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};