算法1

(暴力枚举) $O(n^2)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 暴力枚举
        int n = nums.size();                  // n + 1个数
        for(auto e : nums)
        {
            if(e < 1 && e > n - 1)
            return -1;
        }

        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(nums[i] == nums[j])
                    return nums[i];
            }
        }

        return -1;
    }
};

算法2

(分治法) $O(nlogn)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 分治法
        int n = nums.size();          // n 表示数组的长度
        int l = 1, r = n - 1;
        while(l < r)
        {
            int mid = (r - l) / 2 + l;     // 区间划分[l, mid], [mid + 1, r]

            int count = 0;            // 统计数组中位于左半区间的数的个数[l ,mid]
            for(auto e : nums)
            {
                if(l <= e && e <= mid)
                    count++;
            }

            if(count > mid - l + 1)
                r = mid;
            else 
                l = mid + 1;
        }

        return l;
    }
};