[!info] related notes 算法面试题型 MOC 二分查找

寻找重复数

题目

287. 寻找重复数 - 力扣（LeetCode）

思路（值域二分）

数组长度为 n + 1，数值范围为 1..n，题目保证只有一个不同数值发生重复，可重复多次。这些前提共同支持下面的判定，不能把它当任意数组的去重方法。

令 count(mid) 表示数组里 <= mid 的元素个数：

• 如果 count(mid) > mid，说明在 1..mid 这 mid 个桶里塞了超过 mid 个数，重复数一定在左侧（含 mid）
• 否则重复数在右侧

在唯一重复数 d 之前，count(mid) ≤ mid；从 d 开始，重复产生的超额大于缺失值数量，count(mid) > mid。因此该布尔判定为 false→true，寻找第一个 true。算法不修改输入，时间 O(n log n)，额外空间 O(1)；不是线性时间解法。

代码（JavaScript）

var findDuplicate = function(nums) {
  let l = 1, r = nums.length - 1; // values in [1, n]
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    let cnt = 0;
    for (const x of nums) {
      if (x <= mid) cnt++;
    }
    if (cnt > mid) r = mid;
    else l = mid + 1;
  }
  return l;
};