寻找重复数

以你之姓@ 2023-02-12 15:24 119阅读 0赞

闲着无聊的时候看了一个力扣上的题，感觉还可以，记录一下，也和大家分享一下解题的思路：

题目：

给定一个包含 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) 。  
数组中只有一个重复的数字，但它可能不止重复出现一次

解题思路：

二分法  
按题目表达，设数组长度为nn，则数组中元素∈\[1,n−1\]，且只有一个重复元素。一个直观的想法，设一个数字k∈\[1,n−1\]，统计数组中小于等于k的数字的个数count：

若count<=k，说明重复数字一定在(k,n-1\]的范围内。  
若count>k，说明重复数字一定在\[0,k\]的范围内。  
利用这个性质，我们使用二分查找逐渐缩小重复数字所在的范围。

初试化左右 数字 边界left=1,right=n-1  
循环条件left<right  
mid=(left+right)//2  
按照性质，统计数组中小于等于mid的元素个数count  
若 count<=mid，说明重复数字一定在(mid,right\]的范围内。令left=mid+1  
若count>mid，说明重复数字一定在\[left,mid\]的范围内。令right=mid。  
返回left

代码展示：

class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            left = 1
            right = len(nums) - 1
            while(left<right):
                mid=(left+right)//2
                count=0
                for num in nums:
                    if(num<=mid):
                        count+=1
                if(count<=mid):
                    left=mid+1
                else:
                    right=mid
            return left

参考：力扣作者：wu\_yan\_zu