题目要求:给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。
思路:起码有两个数相同,根据二分查找,通过统计哪个区间个数多肯定就有重复的。
class Solution {
public int duplicateInArray(int[] nums) {
int n= nums.length;
//抽屉原理 分治思想
int l = 1, r = n-1;
while(l < r){
int mid = (l + r)/2; // 划分的区间:[l, mid], [mid + 1, r]
int count=0; //个数
for(int x : nums){ //x为数组中的值
if(x >= l && x <= mid){
++count;
}
}
if (count > mid - l + 1) {//左区间个数多
r = mid; //左区间
} else {
l = mid + 1; //右区间
}
}
return r;
}
}
我去