class Solution {
public int duplicateInArray(int[] nums) {
if(nums.length == 1) {
return nums[0];
}
return dfs(nums,1,nums.length - 1);
}
public int dfs(int[] arr, int left, int right) {
if(left == right) {
return left;
}
int mid = (left+right) >> 1;
int tol = 0;
for(int i = 0; i < arr.length; i) {
if(arr[i] <= mid && arr[i] >= left) {
tol;
}
}
return tol > mid-left+1 ? dfs(arr,left,mid) : dfs(arr,mid + 1,right);
}
}
1.将n+1个数字(1——n) 放到1-n个坑中
2.如果将1-n数组一分为2,那么重复的数字必然在其中一边 left~mid mid+1 ~ right;
3.数字范围在其中一边的个数大于坑位,则一定又重复,反之则不一定