寻找重复数 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

想象有一个 $n + 1$ 个节点的图，节点编号从 $0$ 到 $n$ 。

对 $i = 0, 1, 2, \dots, n$ ，连一条从 $i$ 到 $nums [i]$ 的有向边，可以得到一个有向图。

每个节点的入度，就是这个节点在 $nums$ 中的出现次数。重复元素的入度大于 $1$ 。上图中的节点 $2$ 的入度为 $2$ ，所以 $2$ 是重复元素。

如何找到入度大于 $1$ 的节点？

在每个节点的出度都是 $1$ 的情况下， $n + 1$ 个点 $n + 1$ 条边的有向图，又叫内向基环森林，每个连通块都恰好有一个环。

由于 $nums [i] \geq 1$ ，所以节点 $0$ 的入度是 $0$ ，不在环上。从节点 $0$ 出发，进入基环，基环的入环口，就是入度大于 $1$ 的节点。

⚠注意：如果从非 $0$ 节点出发，可能无法找到答案。如下图，如果从节点 $3$ 出发，无法找到入度大于 $1$ 的节点。

考察包含节点 $0$ 的连通块，其形状和 142. 环形链表 II 是一样的，所以都可以用快慢指针解决，详见我的题解，包含图解和视频讲解。

这两题的联系如下表，注意 $i$ 和 $nums [i]$ 都是节点。

142. 环形链表 II	287. 寻找重复数
链表节点 $node$	$i$
下一个节点 $node . next$	$nums [i]$
头节点 $head$	$0$
入环口	重复元素

在链表中，我们的移动方式是从节点 $node$ 移动到下一个节点 $node . next$ 。

在数组中，我们的移动方式是从节点 $i$ 移动到节点 $nums [i]$ 。由于数组长度是 $n + 1$ ，而 $nums [i] < n + 1$ ，所以不会下标越界。

Python 解法1C++ 解法1

python

# 代码逻辑同 142. 环形链表 II
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0  # 0 一定不在环上，适合作为起点
        while True:
            slow = nums[slow]  # 等价于 slow = slow.next
            fast = nums[nums[fast]]  # 等价于 fast = fast.next.next
            if fast == slow:  # 快慢指针移动到同一个节点
                break

        head = 0  # 再用一个指针，从起点出发
        while slow != head:
            slow = nums[slow]
            head = nums[head]
        return slow  # 入环口即重复元素

cpp

// C++ 版待补充

C++ 解法2

cpp

// 代码逻辑同 142. 环形链表 II
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0; // 0 一定不在环上，适合作为起点
        while (true) {
            slow = nums[slow]; // 等价于 slow = slow.next
            fast = nums[nums[fast]]; // 等价于 fast = fast.next.next
            if (fast == slow) { // 快慢指针移动到同一个节点
                break;
            }
        }

        int head = 0; // 再用一个指针，从起点出发
        while (slow != head) {
            slow = nums[slow];
            head = nums[head];
        }
        return slow; // 入环口即重复元素
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。理由见【基础算法精讲 07】。
空间复杂度： $O (1)$ 。

进阶问题

问：如何证明 $nums$ 中至少存在一个重复的数字?

答：视作有 $n + 1$ 个球和 $n$ 个抽屉，第 $i$ 个球放入第 $nums [i]$ 个抽屉。根据抽屉原理（鸽巢原理），存在一个抽屉至少有两个球，这个抽屉的编号即重复元素。

专题训练

见下面链表题单的「§1.6 快慢指针」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

进阶问题 ​

专题训练 ​

分类题单 ​

复杂度分析

进阶问题

专题训练

分类题单