287. 寻找重复数#

大家好！今天我们来探索一个既有挑战性又充满智慧的问题——寻找重复数（Find the Duplicate Number）。这个问题看似简单，实则暗藏玄机，需要我们运用巧妙的思路才能高效解决。让我们一步步揭开它的奥秘，探索多种精彩的解法！

🌟 寻找重复数：谁是那个出现两次的数字？#

在一个包含 n+1 个整数的数组中，所有数字都在 1 到 n 之间（包括1和n），这意味着数组中至少有一个重复数字。我们的任务就是找出这个”神秘访客”——那个重复出现的数字。

问题描述#

题目目标#

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内。可知至少存在一个重复的整数，请你找出这个重复的数。题目要求不能修改数组，并尽量只使用常量级额外空间。

示例 1#

输入： nums = [1,3,4,2,2] 输出： 2 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

🎯 问题描述：找出数组中唯一的重复元素#

给定一个包含 n+1 个整数的数组 nums，其数字都在 1 到 n 之间（包括1和n），请找出唯一的重复出现的整数。

注意：

1. 你不能修改数组（假设数组是只读的）
2. 你必须只使用 O(1) 的额外空间
3. 你的运行时间复杂度应该小于 O(n²)
4. 数组中只有一个重复的数字，但它可能重复出现多次

例如：

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

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

🚶‍♀️ 从例子开始：理解问题本质#

让我们先来看几个具体的例子，试着找找规律：

例子1: [1,3,4,2,2]

• 这里有5个元素，范围是1到4
• 通过观察我们发现2出现了两次
• 其他数字1,3,4各出现一次

例子2: [3,1,3,4,2]

• 这里有5个元素，范围是1到4
• 通过观察我们发现3出现了两次
• 其他数字1,2,4各出现一次

我们注意到，在长度为n+1的数组中，元素值的范围是1到n，如果没有重复，每个数字应该只出现一次。但因为数组长度是n+1，根据鸽笼原理，必定有一个数字至少重复一次。

🧠 直观思路与挑战#

最直观的方法是什么？可能是排序后找相邻相同元素，或使用哈希表记录每个数字出现的次数。但题目有额外限制：

1. 不能修改数组
2. 只能使用O(1)额外空间
3. 时间复杂度要小于O(n²)

这些限制排除了排序法（会修改数组）和哈希表法（需要O(n)额外空间）。那么，我们需要寻找更巧妙的方法。

🔍 探索规律：如何巧妙地找到重复数？#

我们来思考几种可能的方法，看看它们是否满足题目的所有要求：

方法1：二分查找思路#

我们知道数字范围是1到n，可以用二分查找的思想来缩小范围。

假设我们的例子是 [1,3,4,2,2]：

1. 数字范围是1到4，中间值是2
2. 计算数组中小于等于2的数字个数：[1,2,2] -> 3个
3. 正常情况下，1到2范围内应该有2个数，但我们有3个
4. 说明重复数字在1到2范围内，继续二分查找…

让我们完整模拟一次：

• 初始范围：[1,4]，中值：2
• 统计≤2的元素：[1,2,2] -> 3个（大于2）
• 缩小范围到：[1,2]，中值：1
• 统计≤1的元素：[1] -> 1个（等于1）
• 缩小范围到：[2,2]，即找到重复数2

方法2：快慢指针（Floyd判圈算法）#

这个方法最为巧妙！我们可以把数组看作一个链表，其中索引i指向的值nums[i]就是下一个节点的索引。

例如 [1,3,4,2,2]：

• 从索引0开始，值是1，下一个访问索引1
• 索引1的值是3，下一个访问索引3
• 索引3的值是2，下一个访问索引2
• 索引2的值是4，下一个访问索引4
• 索引4的值是2，下一个访问索引2…

现在注意到索引4再次指向了索引2，形成了一个环！而环的入口就是重复的数字。

让我们直观模拟：

1. 从索引0出发：0 -> 1 -> 3 -> 2 -> 4 -> 2（发现环）
2. 重复数字就是环的入口：2

再看例子 [3,1,3,4,2]：

1. 从索引0出发：0 -> 3 -> 4 -> 2 -> 3（发现环）
2. 重复数字就是环的入口：3

这正是我们要找的重复数字！

🏆 方法实现：从思路到代码#

二分查找法实现#

class Solution {
    public int findDuplicate(int[] nums) {
        // left/right 表示当前二分的“数字范围”，不是数组下标范围
        int left = 1; // 最小可能值
        int right = nums.length - 1; // 最大可能值

        // 当 left == right 时，范围收敛到唯一答案
        while (left < right) {
            // 取中间值，使用该写法避免 (left + right) 溢出
            int mid = left + (right - left) / 2;

            // 计算小于等于mid的元素个数
            // count 用于统计数组中 <= mid 的数字有多少个
            int count = 0;
            for (int num : nums) {
                // 如果当前数字不大于 mid，则计入左半区统计
                if (num <= mid) {
                    count++;
                }
            }

            // 如果计数大于mid，说明重复元素在左半部分
            if (count > mid) {
                // 收缩右边界到 mid，继续在 [left, mid] 查找
                right = mid;
            } else {
                // 否则在右半部分
                // 收缩左边界到 mid+1，继续在 [mid+1, right] 查找
                left = mid + 1;
            }
        }

        // 循环结束时 left == right，该值即为重复数字
        return left; // 此时left==right就是重复元素
    }
}

时间复杂度：O(n log n)，二分查找需要O(log n)次迭代，每次迭代需要O(n)时间统计
空间复杂度：O(1)，只使用了常数额外空间

快慢指针法实现（Floyd判圈算法）#

class Solution {
    public int findDuplicate(int[] nums) {
        // 阶段1：找到环中的相遇点
        // slow 每次走 1 步，fast 每次走 2 步
        // 初始都从 nums[0] 出发
        int slow = nums[0];
        int fast = nums[0];

        do {
            // 慢指针前进一步
            slow = nums[slow]; // 慢指针走一步
            // 快指针前进两步
            fast = nums[nums[fast]]; // 快指针走两步
            // do-while 保证至少执行一次，直到二者在环内相遇
        } while (slow != fast);

        // 阶段2：找到环的入口
        // 把 slow 重置到起点，fast 留在相遇点
        slow = nums[0]; // 重置慢指针到起点
        // 两指针都每次走一步，再次相遇的位置就是环入口
        while (slow != fast) {
            slow = nums[slow]; // 慢指针走一步
            fast = nums[fast]; // 此时快指针也走一步
        }

        // 环入口对应的数值就是重复数字
        return slow; // 环的入口就是重复数
    }
}

时间复杂度：O(n)，只需要遍历数组常数次
空间复杂度：O(1)，只使用了常数额外空间

🎬 详细图解：可视化理解算法#

图解二分查找法：#

以 [1,3,4,2,2] 为例：

1. 范围：[1,4]，中值：2

   • 统计≤2的元素：[1,2,2] -> 3个
   • 3>2，说明重复元素在1到2范围内

2. 范围：[1,2]，中值：1

   • 统计≤1的元素：[1] -> 1个
   • 1=1，说明重复元素在2到2范围内

3. 范围：[2,2]

   • 找到重复元素：2！

图解快慢指针法：#

把 [1,3,4,2,2] 看作链表：

索引：0 -> 1 -> 3 -> 2 -> 4 ↴
值：  1    3    2    4    2 |
      ↑                     |
      +---------------------+

1. 阶段1：找到环中的相遇点

   • 初始：slow = 1, fast = 1
   • 第1步：slow = nums[1] = 3, fast = nums[nums[1]] = nums[3] = 2
   • 第2步：slow = nums[3] = 2, fast = nums[nums[2]] = nums[4] = 2
   • 相遇于索引2，值为4

2. 阶段2：找到环的入口

   • 重置slow = nums[0] = 1
   • slow和fast同时移动，每次一步：
     • slow: 1 -> 3 -> 2
     • fast: 4 -> 2
   • 相遇于索引2，值为4

3. 环的入口对应的值：2

🔬 为什么算法有效？#

二分查找法为什么有效？#

对于1到n内的每个数k，如果数组中小于等于k的元素数量大于k，那么根据鸽笼原理，重复元素一定在1到k范围内。通过不断缩小这个范围，最终我们可以精确定位到重复元素。

快慢指针法为什么有效？#

Floyd判圈算法的核心在于：

1. 如果链表中有环，快慢指针一定会在环内某点相遇
2. 从相遇点和起点同时出发，两指针相遇的地方就是环的入口

在这个问题中，因为值在1到n之间而索引是0到n，所以不会访问到数组外，且一定会形成环。而环的入口就是重复元素，因为这是唯一一个至少有两个不同索引指向的值。

🌱 扩展思考：如果有多个重复元素？#

如果数组中有多个重复元素，我们的算法需要如何修改？

对于二分查找法，它仍然可以找到一个重复元素，但不一定是所有重复元素。

对于快慢指针法，由于可能形成多个环，它只能找到一个重复元素，且我们无法保证哪个重复元素会被找到。

要找出所有重复元素，我们可能需要放宽空间限制，使用哈希表来记录各元素出现次数。

🌐 实际应用：查重的智慧#

寻找重复数的思想在现实中有广泛应用：

• 数据去重：数据库操作、文件系统中的文件去重
• 循环检测：检测图或链表中的循环
• 错误检查：检测系统中的重复错误
• 生物信息学：DNA序列中的重复片段检测

💯 解题心得：巧思胜于蛮力#

寻找重复数问题展示了一个重要的算法设计思想：针对特定约束，寻找巧妙的解法。

• 二分查找法利用了重复元素对计数的影响
• 快慢指针法则将问题转化为找链表环入口
• 当面临空间和时间的双重约束时，数学性质和问题转化往往是关键

🎓 面试小贴士#

面试中遇到”寻找重复数”问题，建议按以下步骤回答：

1. 先分析题目约束，指出为什么简单方法（排序、哈希表）不适用
2. 提出二分查找的思路，解释其工作原理和时间复杂度
3. 介绍快慢指针法，解释如何将数组视为链表，以及如何找到环的入口
4. 用一个具体例子手动模拟算法流程，加深面试官的理解
5. 讨论两种方法的优缺点：二分查找更直观但速度较慢，快慢指针法更高效但需要理解Floyd判圈算法

🤔 思考题#

如果数组中的数字范围改为0到n-1（而不是1到n），且仍然有n+1个数字，如何修改我们的算法来找到重复元素？

寻找重复数是一个看似简单却充满智慧的问题。通过将问题转化或利用数学性质，我们找到了不需要额外空间且高效的解法。这个问题不仅锻炼了我们的算法思维，也提醒我们在约束条件下寻找创新方法的重要性。希望这次探讨能为你的算法之旅增添一份启发！

💪 练习建议#

想要巩固对这个问题的理解，建议尝试：

1. 手动模拟二分查找和快慢指针两种方法解决不同的例子
2. 尝试理解并证明为什么快慢指针相遇后，再从起点和相遇点同时出发能找到环入口
3. 探索问题的变体，如找出所有重复元素、处理数字范围变化等情况

记住，算法的精髓在于理解背后的数学原理和思想方法。当你能从基本原理出发，推导出解决方案，你就真正掌握了这个问题！