Leetcode之二分法专题-287. 寻找重复数(Find the Duplicate Number)
给定一个包含 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) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。
分析题目,给一个n+1大小的数组,数组是从1-n之间的,那这题我们的二分规则可以按照以下步骤:
- 左端点为1,右端点为n,中点为左中位数
二分,得到mid
遍历数组,求小于等于mid的数的出现次数
如果出现次数大于mid,证明多余的数字在这个区间内,在这个区间搜索,保留mid,R = mid
否则,丢弃mid,L = mid +1
AC代码:
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length - 1;
int L = 1;
int R = n;
while(L<R){
int mid = (L+R)>>>1;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i]<=mid) count++;
}
if(count>mid){
R = mid;
}else{
L = mid + 1;
}
}
return L;
}
}