算法思想
本题考查了抽屉原理和二分来做
抽屉原理:n+1 个苹果放在 n 个抽屉里,那么至少有一个抽屉中会放两个苹果。
二分:可否找到一个性质使得一个区间不断的分为一半,最终分为1时就是答案
算法步骤
- 对数的取值范围($1 \sim n$)进行二分,分为左右两个区间$[1,mid]$,$[mid + 1, n]$
- 把$n+1$个数放到$1 \sim n$的区间里,那么左右两个区间一定会有一个区间会有多的数,这个数就是重复的数
- 如果某个区间元素的个数大于区间的长度,那么重复的元素一定在这个区间,然后不断二分,分为1时就是最后的答案
java代码
class Solution {
public int duplicateInArray(int[] nums) {
int l = 1, r = nums.length - 1;
while(l < r)
{
int mid = l + r >> 1; //[1 , mid][mid + 1, n]
int s = 0;
for(int x : nums)
if(x >= l && x <= mid) s ++; //统计左区间元素的个数
if(s > mid - l + 1) r = mid; //元素的个数大于区间的长度,说明哪个区间就有重复的元素
else l = mid + 1;
}
return r;
}
}