题目描述

blablabla

样例

blablabla

算法1

(抽屉原理) $O(n^2)$

blablabla

时间复杂度分析：blablabla

Python 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        left, right = 1, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            count = 0
            for x in nums:
                if x >= left and x <= mid:
                    count += 1
            if count > mid - left + 1:
                right = mid
            else:
                left = mid + 1
        return right