算法

(整数二分模板) $O(nlogn)$

按数组里数的大小进行二分而不是数的下标
把区间划分为[l,mid],[mid+1,r]
统计左半边个数，如果大于区间长度说明有重复元素，将区间更新为[l,mid]，反之更新为[mid+1,r]

Python3 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        l = 1
        r = len(nums) - 1
        while l < r:
            mid = l + r >> 1
            # 统计左半边数的个数
            s = 0
            for i in nums:
                if l <= i <= mid:
                    s += 1
            if s > mid - l + 1:  # 区间长度
                r = mid
            else:
                l = mid + 1
        return l