寻找重复数

在值域 1..n 的 n+1 个数中如何用二分找重复数？

• 条件: 数组长度 n+1, 元素取值在 [1, n], 必有一个重复值; 要求不修改数组且只用常数空间;
• 判定: 统计数组中小于等于 mid 的元素个数 count;
• count <= mid 说明 [1, mid] 中没有重复, left = mid + 1;
• 否则重复值落在 [1, mid] 中, right = mid;

为什么这个判定成立？

• [1, mid] 中只有 mid 个互不相同的整数;
• 若重复值落在 [1, mid] 中, 则落在该区间的元素个数必然大于 mid;
• 因此 count > mid 等价于重复值在左半区间;

寻找重复数如何实现？

function findDuplicate(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    let count = 0;
    for (const num of nums) {
      if (num <= mid) count++;
    }
    if (count <= mid) left = mid + 1;
    else right = mid;
  }
  return left;
}

寻找重复数的复杂度是多少？

• 时间复杂度: O(n log n), 每轮二分需要一次 O(n) 统计;
• 空间复杂度: O(1);