Title link: www.acwing.com/problem/con…

Analysis of the

  1. O (1) space
  2. Length N + 1 ==> N + 1 Number, the value ranges from 1 to n (n possible values)
  3. Binary: the key ==> binary is the value range of the number, not the index of the array

Code

/ * * *@param {number[]} nums
 * @return {number}* /
var duplicateInArray = function(nums) {
    let l = 1, r = nums.length - 1; // This interval is the range of the number (1 to n).
    while(l < r){
        let mid = l + r >> 1;  // [l mid] [mid+1 r]
        let count = 0; // Count interval numbers
        for(let k of nums){
            if(l <= k && k <= mid) count++;
        }
        if(count > mid - l + 1) r = mid;
        else l = mid + 1;
    }
    
    return l;
    
};
Copy the code