56. LeetCode 287. 寻找重复数

• 标签： 数组 二分查找
• 难度： 中等

• 题目描述

• 我的解法

用二分法在 [1,n] 间搜索, 先求中点 mid, 遍历数组统计小于等于 mid 的个数， 记为 cnt. 若 cnt > mid, 则重复值在 [low, mid]之间 , 否则在 (mid, high] 之间 .

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high = 1, len(nums) - 1
        while(low < high):
            mid = (low + high) // 2
            cnt = 0
            for n in nums:
                if n<= mid:
                    cnt += 1
            if cnt > mid:
                high = mid
            else:
                low = mid + 1
        return low

• 其他解法

暂略。