分析
1、 O(1)的空间
2、 长度 n + 1 ==> n + 1 个数字, 取值 1~n (n种取值) 抽屉原理,必然存在重复
3、 二分: 关键==>二分的是数的取值范围,而不是数组的下标
Code
/**
* @param {number[]} nums
* @return {number}
*/
var duplicateInArray = function(nums) {
let l = 1, r = nums.length - 1; //这个区间是 数的取值范围 (1~n)
while(l < r){
let mid = l + r >> 1; // [l mid] [mid+1 r]
let count = 0; //统计区间数量
for(let k of nums){
if(l <= k && k <= mid) count++;
}
if(count > mid - l + 1) r = mid;
else l = mid + 1;
}
return l;
};