287.寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

链接：https://leetcode.cn/problems/find-the-duplicate-number

二分查找解法

二分法的思路是寻找下标和nums[i]的关系。nums中最大元素值不会超过n-1,那么可以把nums里的元素值作为另一数组的下标。
假设有个数组less ， less[i] 代表 nums里 <= i 的数字的个数，由于nums里必定有重复，所以less[i]中的value在某个 i 开始必定存在 less[i] > i 。
根据题目，nums的范围在 [1,n]， 写一个用例nums= [1,2,2,3,4]， 数组的长度是5， 则数组内最大元素不会超过4。
那么可以得出less的值是这样的 [1,3,4,5]

可以看出从 i=2 开始 value 会大于下标，这个下标就是我们在nums中寻找的result。由于less的下标是单调递增的，所以可以用二分查找去找到第一个value大于下标的值，然后返回。

/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
  nums.sort()
  let l = 1
  let r = nums.length - 1
  /**
  0 1 2 3 4 5 6
  0 2 3 4 5 6 7  
  1 1 2 4 3 5 6
  0 1 2 3 4 5 6
  */
  let res
  while(l<=r) {
    let mid = Math.floor((l+r) /2)
    let less = 0
    for(let i=0; i<nums.length;i++) {
      if (nums[i] <= mid) less++
    }
    if (less > mid) {
      res = mid
      r = mid - 1
    } else {
      l = mid + 1
    }
  }
  return res
};