287. 寻找重复数：位运算解法

LeetCode 原题链接

题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内。

假设 nums 只有一个重复的整数，请找出这个重复的数。

要求：

  • 不能修改数组 nums。
  • 只使用常数级额外空间。

示例：

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

1. 题型判断

除了快慢指针，本题还可以使用位运算。

核心思路是：既然数字都在 [1, n]，那么正常情况下，数组应该包含 1 到 n 这些数各一次。但现在 nums 的长度是 n + 1，多出来的那部分一定来自重复数字。

我们可以逐个二进制位比较：

  • nums 中这一位为 1 的数量。
  • [1, n] 中这一位为 1 的数量。

如果某一位上，nums 中 1 的数量更多，说明重复数字在这一位上是 1。

把这些多出来的二进制位拼起来，就是重复数字。

2. 位含义

使用二进制位来还原重复数字。

  • bit：当前检查的二进制位。
  • numsCount：nums 中第 bit 位为 1 的数字数量。
  • rangeCount：1 到 n 中第 bit 位为 1 的数字数量。
  • ans：最终还原出的重复数字。

判断某个数字 num 的第 bit 位是否为 1：

(num >> bit) & 1

如果结果是 1，说明这一位存在。

3. 维护规则

设 n = nums.length - 1。

从低位到高位枚举每一个二进制位：

  1. 遍历 nums，统计当前位为 1 的个数，得到 numsCount。
  2. 遍历 [1, n]，统计当前位为 1 的个数，得到 rangeCount。
  3. 如果 numsCount > rangeCount，说明重复数字当前位是 1，把这一位加入答案。

加入答案的方式：

ans |= 1 << bit;

4. 答案更新时机

每一位统计完成后，都可以判断这一位是否属于重复数字。

如果：

numsCount > rangeCount

说明重复数字在当前位上贡献了额外的 1，于是更新：

ans |= 1 << bit;

所有二进制位处理完成后，ans 就是重复数字。

5. 边界条件与易错点

边界条件：

  • nums.length = n + 1，所以 n = nums.length - 1。
  • 数字范围是 [1, n]，只需要统计到 n 的最高二进制位。
  • 题目保证存在重复数，因此最后一定能还原出答案。

易错点：

  • 统计 [1, n] 时不能从 0 开始，因为题目数字范围不包含 0。
  • 判断当前位时要写成 ((num >> bit) & 1) === 1，避免把位运算结果和布尔值混在一起。
  • 只有当 numsCount > rangeCount 时，当前位才应该加入答案。
  • 位运算不会修改原数组，满足题目要求。

6. 代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
  const n = nums.length - 1;
  let ans = 0;
  let maxBit = 0;

  while ((n >> maxBit) !== 0) {
    maxBit++;
  }

  for (let bit = 0; bit < maxBit; bit++) {
    let numsCount = 0;
    let rangeCount = 0;

    for (let i = 0; i < nums.length; i++) {
      if (((nums[i] >> bit) & 1) === 1) {
        numsCount++;
      }
    }

    for (let num = 1; num <= n; num++) {
      if (((num >> bit) & 1) === 1) {
        rangeCount++;
      }
    }

    if (numsCount > rangeCount) {
      ans |= 1 << bit;
    }
  }

  return ans;
};

7. 复杂度分析

  • 时间复杂度：O(n log n)。需要枚举 n 的每一位，位数约为 log n，每一位都遍历 nums 和 [1, n]。
  • 空间复杂度：O(1)。只使用了计数变量和答案变量，没有修改原数组。

为什么这个方法成立

以 nums = [1,3,4,2,2] 为例，n = 4，正常范围是 [1,2,3,4]。

看二进制：

1 = 001
2 = 010
3 = 011
4 = 100

nums 比 [1,4] 多出来的数字是一个额外的 2。

逐位统计：

第 0 位，也就是最右边这一位：

正常范围 [1,2,3,4]

1 = 001  第 0 位是 1
2 = 010  第 0 位是 0
3 = 011  第 0 位是 1
4 = 100  第 0 位是 0

第 0 位共有 2 个 1
实际数组 [1,3,4,2,2]

1 = 001  第 0 位是 1
3 = 011  第 0 位是 1
4 = 100  第 0 位是 0
2 = 010  第 0 位是 0
2 = 010  第 0 位是 0

第 0 位共有 2 个 1

实际数组没有比正常范围多，所以重复数字第 0 位不是 1。

第 1 位：

正常范围 [1,2,3,4]

1 = 001  第 1 位是 0
2 = 010  第 1 位是 1
3 = 011  第 1 位是 1
4 = 100  第 1 位是 0

第 1 位共有 2 个 1
实际数组 [1,3,4,2,2]

1 = 001  第 1 位是 0
3 = 011  第 1 位是 1
4 = 100  第 1 位是 0
2 = 010  第 1 位是 1
2 = 010  第 1 位是 1

第 1 位共有 3 个 1

实际数组比正常范围多了一个 1，所以重复数字第 1 位是 1。

第 2 位：

正常范围 [1,2,3,4]

1 = 001  第 2 位是 0
2 = 010  第 2 位是 0
3 = 011  第 2 位是 0
4 = 100  第 2 位是 1

第 2 位共有 1 个 1
实际数组 [1,3,4,2,2]

1 = 001  第 2 位是 0
3 = 011  第 2 位是 0
4 = 100  第 2 位是 1
2 = 010  第 2 位是 0
2 = 010  第 2 位是 0

第 2 位共有 1 个 1

实际数组没有比正常范围多，所以重复数字第 2 位不是 1。

最后得到：

第 2 位: 0
第 1 位: 1
第 0 位: 0

拼起来是：

010

也就是十进制的 2。

统计所有位之后，就能把重复数字 2 的二进制形态 010 还原出来。