Find the Duplicate Number

287. 寻找重复数

分析

将问题抽象为一个带环的链表问题：

数组中的每个元素都可以看作指向下一个索引的指针：元素的值 nums[i] 指向索引 nums[i]
因为数组中有重复的数字，这意味着某些索引会形成一个环。我们需要找到这个环的入口点，即重复的数字

利用 Floyd 判圈算法（龟兔赛跑算法）可以高效解决这个问题：

阶段 1：找到快慢指针的相遇点
- 定义两个指针：慢指针 a 每次移动一步，快指针 b 每次移动两步
- 两个指针一定会在环中相遇。
阶段 2：找到环的入口点
- 将其中一个指针 a 重新指向起点 0 ，另一个指针 b 保持在相遇点
- 两个指针每次都移动一步，相遇时的点即为环的入口点，也就是重复的数字

时间复杂度

快慢指针每次只移动一步或两步，最多经过两次遍历（一次寻找环，一次定位入口），时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution
{
public:
    int findDuplicate(vector<int>& nums)
    {
        int a = 0, b = 0;  // 初始化快慢指针
        while (true)
        {
            a = nums[a];       // 慢指针每次走一步
            b = nums[b];       // 快指针第一次走一步
            b = nums[b];       // 快指针第二次走一步

            // 快慢指针相遇，退出循环
            if (a == b)
            {
                a = 0;         // 慢指针从起点开始
                while (a != b) // 两指针同步移动
                {
                    a = nums[a];
                    b = nums[b];
                }
                return a;      // 相遇点即为环入口，即重复数字
            }
        }
        return -1;  // 理论上不可能到达这里
    }
};