寻找重复数

LeetCode 287：二分值域 + 计数（抽屉原理）定位重复数。

#resource / algorithm #type / howto #status / evergreen #source / leetcode #algo / binary-search #ds / array

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

寻找重复数

题目

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

思路（值域二分）

数组长度为 n+1，数值范围为 1..n。

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

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

这是一个标准的“值域二分 + 单调判定”。

代码（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;
};