Description

将n+1个整数，一一对应[1,n]的抽屉里，那么至少有一个抽屉里放了两个数。对抽屉编号进行二分，每次二分猜编号m。 那么如果n+1个数中，每个<=m的数一一对应到[1,m]的抽屉里，没有重复放，那么抽屉的数量应该是m。 比如[1,2,3,4,5]个抽屉，有6个数，如果是[1,2,3,4,5,5]，那么m取3的时候，抽屉的编号是3，表明前三个抽屉它可以放1，2，3这三个数。此时我们开始从[1,2,3,4,5,5]中逐个看，哪些数能往里头放。 第一个数是1，可以放，第二个数是2，可以放，第三个数是3，可以放。第四个数是4放不进去，第五个数是5，放不进去。第六个数是5，放不进去。刚好放进去的数的个数跟抽屉编号代表的前三个数相等，并没有多放。 假设此时m=5，抽屉的编号是5，表明前五个抽屉它可以放1，2，3，4，5这五个数。此时我们开始从[1,2,3,4,5,5]中逐个看，哪些数能往里头放。 第一个数是1，可以放，第二个数是2，可以放，第三个数是3，可以放。第四个数是4，可以放，第五个数是5，可以放。第六个数是5，可以放。照正常来说，每个抽屉只放1个的话，<=5的数就是5，但是此时<=5的数有6个，说明在m=5的时候前5个数放了6个，有一个抽屉重复放了。 那么重复数一定在[1,5]之间。我们缩小范围，只需要在抽屉[1,5]中找重复数就好了。即此时的[1,n]缩小成了[1,5]。 然后我们继续看，如果m=3，抽屉的编号是3，表明前三个抽屉它可以放1，2，3这三个数。此时我们开始从[1,2,3,4,5,5]中逐个看，哪些数能往里头放。 第一个数是1，可以放，第二个数是2，可以放，第三个数是3，可以放。第四个数是4放不进去，第五个数是5，放不进去。第六个数是5，放不进去。刚好放进去的数的个数跟抽屉编号代表的前三个数相等，并没有多放。 说明编号为3终止的前三个抽屉一定没多放，此时我们缩小查看抽屉的范围，缩小到[4,5]。 我们继续二分，如果m=4，抽屉的编号是4，表明前四个抽屉它可以放1，2，3，4这四个数。此时我们开始从[1,2,3,4,5,5]中逐个看，哪些数能往里头放。 第一个数是1，可以放，第二个数是2，可以放，第三个数是3，可以放。第四个数是4，可以放。第五个数是5，放不进去。第六个数是5，放不进去。刚好放进去的数的个数跟抽屉编号代表的前四个数相等，并没有多放。 说明编号为4终止的前四个抽屉一定没多放，此时我们缩小查看抽屉的范围，缩小到[5]。 我们继续二分，如果m=5，抽屉的编号是5，表明前五个抽屉它可以放1，2，3，4，5这五个数。此时我们开始从[1,2,3,4,5,5]中逐个看，哪些数能往里头放。 第一个数是1，可以放，第二个数是2，可以放，第三个数是3，可以放。第四个数是4，可以放，第五个数是5，可以放。第六个数是5，可以放。此时我们发现5个抽屉放了6个数。 说明5就是我们要找的那个放了重复数的抽屉。

function findDuplicate(nums: number[]): number {
  // 抽屉原理：n个抽屉，n+1个物品，至少有一个抽屉放了2个物品
  // 在这个问题中：
  // - 抽屉：1到n的每个数字
  // - 物品：数组中的n+1个数字

  const n = nums.length - 1;
  let l = 1;
  let r = n;

  while (l < r) {
    // 有1-n个抽屉，m代表前m个抽屉。
    const m = l + Math.floor((r - l) / 2);

    let cnt = 0;

    // 我们尝试看下，前m个抽屉里，要放对应编号的数，能放多少个。正常来说一一对应，那么应该放m个数。cnt === m
    // 如果cnt > m，说明重复的数在[1,m]抽屉里
    for (const x of nums) {
      // 统计nums中小于等于m的数字的个数
      // 如果没重复，最终cnt应该等于m
      // 否则就是cnt > m，说明重复的数在[1,m]之间
      if (x <= m) {
        cnt++;
      }
    }

    if (cnt > m) {
      // 说明重复的数在[1,m]之间
      r = m;
    }
    else {
      // 说明重复的数在[m+1,n]之间
      l = m + 1;
    }
  }

  return r;
}
Copy