（Java）leetcode-287 Find the Duplicate Number

快来打我* 2023-06-15 13:28 22阅读 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) 。  
数组中只有一个重复的数字，但它可能不止重复出现一次。

# 思路1：二分法 #

按题目表达，设数组长度为n，则数组中元素∈\[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  
复杂度分析  
时间复杂度：O(nlog(n))，二分法执行了log(n)次遍历n，因此复杂度为O(nlog(n))。  
空间复杂度：O(1)

> 作者：zhu\_shi\_fu  
> 链接：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-kuai-man-zhi-zhen-zhu-xing-jie-shi-pytho/  
> 来源：力扣（LeetCode）  
> 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

## 代码 ##

// 二分法
    class Solution { 
        public int findDuplicate(int[] nums) { 
        	int left = 1;
        	int right = nums.length-1;
        	while(left < right) { 
        		int count = 0;
                int mid = (left + right) / 2;
        		for(int num : nums) { 
        			if (num <= mid) { 
        				count++;
        			}
        		}
    
        		if (count <= mid) { 
        			left = mid + 1;	
        		} else { 
                    right = mid;
                }
        	}
        	return left;
        }
    }

## 提交结果 ##

![在这里插入图片描述][20191122173324519.png]

# 思路2：双指针 #

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/  
直接上官方解答了，类似leetcode-141，难度上升级了，链表中的环成为了逻辑上的环。

[20191122173324519.png]: https://img-blog.csdnimg.cn/20191122173324519.png