寻找重复数

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

可知至少存在一个重复的整数。

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：

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

解法一（二分查找 + 计数）：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1;
        int right = nums.size() - 1;

        while (left < right)
        {
            int mid = left + (right - left) / 2;
            int count = 0;

            for (int num : nums)
            {
                if (num <= mid)
                {
                    count++;
                }
            }

            if (count > mid)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        return left;
    }
};

解法二（快慢指针）：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];

        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

核心思想

这题不能修改数组，也只能使用 O(1) 额外空间。

所以不能排序，也不能使用哈希集合。

数组长度是 n + 1，但是数字范围只有 [1, n]。

根据抽屉原理，至少有一个数字会重复。

这题最关键的观察是：

可以把数组看成一个“下标指向下一个下标”的链表，重复数字就是环的入口。

因为 nums[i] 的值一定在 [1, n] 范围内，所以可以把：

i -> nums[i]

看成一条指针。

从某个位置不断按照 nums[index] 往下走，一定会进入环。

重复数字对应的位置有多个来源，就像链表中多个节点指向同一个入口，因此可以用快慢指针找环入口。

为什么一定有重复数字

数组中有 n + 1 个数。

每个数都只能在 [1, n] 这 n 个整数中取值。

把 n + 1 个数放进 n 个可能的值里，至少有一个值会被放入两次或更多次。

这就是抽屉原理。

所以题目保证的条件下，重复数字一定存在。

解法一：二分查找 + 计数

这里的二分不是对数组下标二分，而是对数字范围 [1, n] 二分。

假设当前检查范围是 [1, mid]。

统计数组中小于等于 mid 的数字个数：

if (num <= mid)
{
    count++;
}

如果没有重复数字，那么 [1, mid] 这个范围内最多只能有 mid 个数字。

如果：

count > mid

说明 [1, mid] 中的数字数量超过了这个范围本来能容纳的数量。

根据抽屉原理，重复数字一定在 [1, mid] 中。

否则，重复数字就在 [mid + 1, n] 中。

这个方法不会修改数组，也只使用常数额外变量。

不过它每次二分都要遍历整个数组计数，所以时间复杂度是 O(n log n)。

解法二：快慢指针建环

数组可以看成一个特殊链表。

对于下标 i，下一步走到：

nums[i]

因为 nums[i] 一定在 [1, n] 中，所以不会越界。

例如：

nums = [1,3,4,2,2]

从下标 0 开始：

0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> ...

可以看到，2 -> 4 -> 2 形成了一个环。

环的入口是 2，也正好是重复数字。

因此问题转化成：

在一个有环链表中，找到环的入口。

这就可以使用快慢指针。

为什么重复数字是环入口

把每个位置看成节点，每个节点有一条边指向：

nums[i]

因为数组有 n + 1 个位置，但指向的值只有 1 ~ n。

重复数字 x 表示至少有两个不同的位置都指向 x。

这相当于链表中有两个入口汇入同一个节点。

从下标 0 出发不断沿着 nums[index] 走，最终会进入一个环。

第一次进入环的位置，就是那个被多个位置指向的重复数字。

所以找到环入口，就找到了重复数字。

快慢指针过程

第一阶段：让快慢指针在环中相遇。

slow = nums[slow];
fast = nums[nums[fast]];

其中：

• slow 每次走一步
• fast 每次走两步

只要存在环，它们一定会在环中相遇。

第二阶段：找环入口。

把 slow 放回起点：

slow = nums[0];

然后让 slow 和 fast 每次都走一步：

slow = nums[slow];
fast = nums[fast];

它们再次相遇的位置就是环入口，也就是重复数字。

为什么不能使用原地哈希

有些数组题可以通过交换元素，把数字放到对应下标上。

例如把数字 x 放到下标 x - 1。

但本题明确要求：

不修改数组 nums

所以不能通过交换、标记负数、排序等方式改变原数组。

快慢指针只读取数组值，不会写入数组，满足题目要求。

正确性证明

我们证明：快慢指针算法返回的数字就是唯一的重复数字。

结论 1：数组映射一定会形成环

数组中每个值都在 [1, n] 范围内。

所以从任意位置 i 出发，下一步 nums[i] 一定仍然是一个合法下标。

不断沿着：

i -> nums[i]

前进时，由于可能到达的位置只有有限个，最终一定会重复经过某个位置。

一旦重复经过某个位置，就形成了环。

结论 2：环入口对应重复数字

重复数字 x 至少出现两次。

也就是说，至少有两个不同下标 a 和 b，满足：

nums[a] = x
nums[b] = x

在映射图中，这表示有至少两条边指向节点 x。

从下标 0 出发第一次进入环的位置，就是这个被多个路径汇入的位置。

因此环入口就是重复数字。

结论 3：第一阶段快慢指针一定会在环中相遇

进入环后，fast 每次比 slow 多走一步。

环长有限，所以两者之间的相对距离会不断变化，并最终变为 0。

也就是说：

slow == fast

因此第一阶段一定能得到一个环内相遇点。

结论 4：第二阶段两个指针会在环入口相遇

快慢指针第一次相遇后，一个指针从起点出发，另一个指针从相遇点出发。

两者每次都走一步。

根据环形链表入口的结论，它们会在环入口相遇。

由结论 2 可知，环入口就是重复数字。

所以第二阶段返回的值就是重复数字。

得出结论

由结论 1 可知，数组映射一定存在环。

由结论 2 可知，环入口就是重复数字。

由结论 3 可知，快慢指针能找到环中的相遇点。

由结论 4 可知，第二阶段能找到环入口。

因此算法返回的就是唯一重复的整数。

举例理解

以：

nums = [1,3,4,2,2]

为例。

按照 i -> nums[i] 走：

0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> ...

环是：

2 -> 4 -> 2

环入口是 2。

所以重复数字是：

2

再看：

nums = [3,1,3,4,2]

按照映射走：

0 -> 3 -> 4 -> 2 -> 3 -> ...

环入口是 3。

所以重复数字是：

3

复杂度分析

解法一

二分的是数字范围 [1, n]，每次判断都要遍历数组计数。

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)

解法二

快慢指针在线性步数内完成相遇和入口查找。

算法只使用常数个指针变量，并且不修改数组。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

解法二满足进阶要求，是更推荐的做法。