287 寻找重复值

[neptoo]

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

提示：

2 <= n <= 3 * 104

nums.length == n + 1

1 <= nums[i] <= n

nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次。

输入：nums = [1,3,4,2,2]
输出：2

输入：nums = [3,1,3,4,2]
输出：3

输入：nums = [1,1]
输出：1

进阶：

如何证明 nums 中至少存在一个重复的数字?

你可以在不修改数组 nums 的情况下解决这个问题吗？

你可以只用常量级 O(1) 的额外空间解决这个问题吗？

你可以设计一个时间复杂度小于 O(n2) 的解决方案吗？

题解：

只有一个数字重复，但可能重复多次

不修改数组：不能去移动数组，不能排序

常量级空间：不能使用哈希表，不能新建数组再排序

思路：二分查找：除了对索引二分，还有值域二分

数组元素是 1 - n 中的某一个，出现的位置不确定，但值域是确定的。

mid = (1+n)/2 重复值要么在[1, mid] 要么在[mid+1, n]

遍历原数组 统计<=mid的个数 记为k

如果k>mid 则重复值在[1, mid] 否则在[mid+1, n]

eg: 有6个数落在[1,5]之间 该区间只有5个坑位 则说明有重复值

对重复数所在的区间继续二分，直到区间闭合，重复数就找到了。

时间复杂度：二分法O(logN)O(logN)，但二分法内部遍历了一次数组O(N)O(N)，综合为O(NlogN)O(NlogN)

var findDuplicate = (nums) => {
  let k = 1;
  let n = nums.length - 1;
  while (k < n) {
    const mid = (k + n) >> 1; // 求中间索引
    let count = 0;
    for (let i = 0; i <= nums.length; i++) {
      if (nums[i] <= mid) {
        count++;
      }
    }
    if (count > mid) {
      n = mid;
    } else {
      k = mid + 1;
    }
  }
  return k;
};
// console.log(findDuplicate([3,1,3,4,2]));