寻找重复数

题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:

输入: [3,1,3,4,2]
输出: 3
说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number

解题思路

由于本题的说明限制，所以不能使用排序和hash表的操作来进行。但是在实际应用中，考虑的都是空间换时间，最优方法还是直接使用hash表来处理。
由于本题给的n+1个数的范围是从1到n，所以可以考虑使用二分查找来解决
对于一个1到n组成的n+1的数组，如果重复元素是target，那么整个数组中小于等于target的元素个数是大于target的。所以我们随机寻找一个数mid，如果数组中小于等于mid的元素个数大于mid，则说明重复元素是在[left,mid]之间，反之在(mid,rifht]之间

代码

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        left = 1
        right = n-1
        while left<right:
            cnt = 0
            #向下取整
            mid = (left+right)//2
            #求出数组中小于等于mid的元素个数
            for num in nums:
                if num<=mid:
                    cnt+=1
            #如果小于等于mid的元素个数cnt 大于 mid，则说明了重复元素在[left, mid]之间
            if cnt>mid:
                right = mid
            else:
                left = mid+1
        return left