287. 寻找重复数

题目链接（中等）

题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数，返回 这个重复的数。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

数据范围：

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次，其余整数均只出现 一次

进阶：

• 如何证明 nums 中至少存在一个重复的数字？
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

示例

示例 1：

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

示例 2：

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

示例 3：

输入： nums = [3,3,3,3,3]
输出： 3

核心思路

本题的限制很苛刻：

• 不能修改数组；
• 只能用 $O(1)$ 额外空间；
• 进阶要求 $O(n)$ 时间。

朴素解法：

• 排序后相邻比较：$O(n \log n)$，但修改了数组，不符合；
• 哈希集合：$O(n)$ 时间，但 $O(n)$ 空间，不符合。

三种符合要求的解法：

1. 二分查找：在值域 [1, n] 上二分答案，利用 cnt[i] 的单调性，$O(n \log n)$ 时间、$O(1)$ 空间；
2. 二进制按位统计：逐位比较 nums 和 [1, n] 中该位为 1 的个数，$O(n \log n)$ 时间、$O(1)$ 空间；
3. 快慢指针（Floyd 判圈）：把数组视为链表，找环的入口，$O(n)$ 时间、$O(1)$ 空间，满足进阶要求。

---

方法一：二分查找（在值域上二分）

思路及解法

定义 cnt[i] = nums 中小于等于 i 的数的个数。

关键性质：设重复数为 target，则：

• 当 i < target 时，cnt[i] ≤ i；
• 当 i ≥ target 时，cnt[i] > i。

为什么？

• 数组共有 n + 1 个数，取值范围 [1, n]；
• 如果每个数只出现一次，那么 cnt[i] = i；
• 现在有一个数 target 多出现了（至少一次），那么从 target 开始，cnt[i] 会比 i 多至少 1。

所以 cnt[i] 随 i 增大具有单调性，可以用二分查找找到第一个满足 cnt[i] > i 的 i，就是答案。

举例：nums = [1,3,4,2,2]，n = 4

i	cnt[i]（≤ i 的个数）	cnt[i] 与 i 比较
1	1	≤
2	3	>
3	4	>
4	5	>

第一个 cnt[i] > i 的 i = 2，即答案。

二分过程：

• 在 [1, n] 中二分 mid；
• 统计 nums 中 ≤ mid 的个数 cnt；
• 若 cnt ≤ mid，说明 target > mid，l = mid + 1；
• 否则 target ≤ mid，记录答案并 r = mid - 1。

代码

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        n = len(nums)
        l, r = 1, n - 1
        ans = -1

        while l <= r:
            mid = (l + r) // 2
            cnt = sum(1 for x in nums if x <= mid)

            if cnt <= mid:
                l = mid + 1
            else:
                r = mid - 1
                ans = mid

        return ans

复杂度分析

• 时间复杂度：$O(n \log n)$，二分 $O(\log n)$ 次，每次统计 $O(n)$。
• 空间复杂度：$O(1)$，只使用常数个变量。

---

方法二：二进制按位统计

思路及解法

逐位确定重复数的每一位。

关键观察：设 nums 中第 i 位为 1 的个数为 x，数字 [1, n] 中第 i 位为 1 的个数为 y，则：

• 若 target 第 i 位为 1，则 x > y；
• 若 target 第 i 位为 0，则 x ≤ y。

为什么？

假设 target 出现两次，其余数各出现一次：

• target 第 i 位为 1 → x 比 y 大 1；
• target 第 i 位为 0 → x = y。

若 target 出现多次，则某些数字被替换掉：

• 若被替换的数该位为 1、target 该位为 1 → x 不变，仍 > y；
• 若被替换的数该位为 0、target 该位为 1 → x 增加，仍 > y；
• 若被替换的数该位为 1、target 该位为 0 → x 减少，仍 ≤ y；
• 若被替换的数该位为 0、target 该位为 0 → x 不变，仍 ≤ y。

因此逐位判断 x > y 即可还原 target。

代码

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        n = len(nums) - 1             # 值域上限
        bit_max = (n - 1).bit_length()  # 最大位数
        ans = 0

        for bit in range(bit_max):
            x = y = 0
            for i, v in enumerate(nums):
                if v & (1 << bit):
                    x += 1
            for i in range(1, n + 1):
                if i & (1 << bit):
                    y += 1
            if x > y:
                ans |= 1 << bit

        return ans

复杂度分析

• 时间复杂度：$O(n \log n)$，枚举 $\log n$ 位，每位遍历 $O(n)$。
• 空间复杂度：$O(1)$。

---

方法三：快慢指针（Floyd 判圈）✅ 推荐

思路及解法

关键转化：把数组 nums 视为一个链表，位置 i 连一条 i → nums[i] 的边。

由于存在重复数字 target，至少有两个不同的位置指向同一个位置 target，所以这个「链表」中一定存在环，且环的入口就是 target。

这样本题就等价于 LC 142. 环形链表 II：找环的入口。

Floyd 判圈算法：

1. 慢指针 slow 每次走一步，快指针 fast 每次走两步；
2. 两者一定会在环内相遇；
3. 相遇后，让 slow 重置为起点 0，与 fast 同速前进；
4. 它们会在环的入口相遇，即答案。

为什么这样能找到环的入口？

设：

• $a$ = 起点到环入口的距离；
• $b$ = 环入口到相遇点的距离；
• $c$ = 相遇点回到环入口的距离；
• $L = b + c$ 为环长。

相遇时：

• slow 走了 $a + b$ 步；
• fast 走了 $2(a+b) = a + b + kL$ 步（多绕了 $k$ 圈）。

化简：$a + b = kL$，即 $a = kL - b = (k-1)L + c$。

所以从起点走 $a$ 步和从相遇点走 $c$（可能再加几圈）会同时到达环入口，两者必在环入口相遇。

代码

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # 第一步：快慢指针找相遇点
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # 第二步：一个从头出发，一个从相遇点出发，同速前进
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

复杂度分析

• 时间复杂度：$O(n)$，Floyd 判圈算法是线性的。
• 空间复杂度：$O(1)$，只用两个指针。

---

三种方法对比

方法	时间	空间	是否满足进阶	特点
二分查找	$O(n \log n)$	$O(1)$	❌	思路巧妙，但时间不是线性
二进制按位	$O(n \log n)$	$O(1)$	❌	按位还原，比较「偏门」
快慢指针	$O(n)$	$O(1)$	✅	最优解，也最优雅

推荐：

• 面试：首选快慢指针，时间 $O(n)$、空间 $O(1)$，满足进阶要求；
• 开场思路：可以先讲二分，因为它更容易想到；
• 加分：能讲清「把数组视为链表，找环入口」这个转化，非常加分。

---

关键细节

1. 二分法的单调性

cnt[i] 随 i 增大是单调不减的，且满足：

• i < target 时 cnt[i] ≤ i；
• i ≥ target 时 cnt[i] > i。

所以可以用二分找第一个 cnt[i] > i 的位置。

2. 快慢指针为什么不会死循环

因为数组中一定存在环（由题目保证：n + 1 个位置、n 个值、至少一个重复）。Floyd 判圈算法保证在有环时一定能相遇。

3. 快慢指针的初始化

本题不能用 slow = fast = head + 先比较的写法（会导致初始即相等）：

slow = fast = 0
while True:
    slow = nums[slow]
    fast = nums[nums[fast]]
    if slow == fast:
        break

因为起点 0 和 nums[0] 逻辑上不相同，所以先移动再比较。用 while True + break 是最清晰的写法。

4. 为什么「不修改数组」

• 排序会修改数组；
• 快慢指针只读取 nums[i]，不写；
• 二分只统计个数，不写；
• 二进制只统计各位，不写。

三种方法都满足「不修改数组」。

5. 与 LC 142 环形链表 II 的关系

本题的解法就是 LC 142 的完全套用：

• 数组下标 = 链表节点；
• nums[i] = next 指针；
• 重复数字 = 环的入口。

如果对 LC 142 熟悉，本题可以直接秒。

---

总结

• 本质：n + 1 个数填在 n 个位置，一定有一个重复数；
• 二分：
  • 在值域 [1, n] 上二分；
  • 利用 cnt[i] 的单调性找第一个 cnt[i] > i；
  • $O(n \log n)$、$O(1)$ 空间；
• 二进制按位：逐位比较 nums 和 [1, n] 中该位 1 的个数，$O(n \log n)$；
• 快慢指针（最优）：
  • 把数组视为链表：i → nums[i]；
  • 重复数即环的入口；
  • Floyd 判圈算法找入口，$O(n)$、$O(1)$；
• 通用套路：「数组 + 重复数」问题，如果能容忍 $O(n \log n)$，用二分；要求 $O(n)$，用快慢指针。

相关题目

• LC 141. 环形链表（判断是否有环）
• LC 142. 环形链表 II（找环的入口）
• LC 442. 数组中重复的数据（找所有重复数，可修改数组）
• LC 448. 找到所有数组中消失的数字（原地哈希）
• LC 剑指 Offer 03. 数组中重复的数字（可修改数组）