287.寻找重复数

Bin大约 4 分钟

题目描述

给定一个包含 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

解题思路：快慢指针 (Floyd 判圈算法)

这道题的限制条件非常苛刻：不能修改原数组，并且空间复杂度要求为 O(1)。这意味着我们不能使用排序、哈希表等常规方法。

我们可以换一个角度来思考这个问题。数组中的数字范围是 [1, n]，而数组的长度是 n + 1。我们可以将数组中的每个索引 i 和它对应的值 nums[i] 看作是一个映射关系 i -> nums[i]。由于 nums 中的值也在索引范围内（虽然不完全对应），我们可以将这个数组想象成一个链表。

节点：数组的索引 0, 1, ..., n
指针：从索引 i 指向索引 nums[i]

例如，对于 nums = [1, 3, 4, 2, 2]：

0 -> nums[0] 即 0 -> 1
1 -> nums[1] 即 1 -> 3
2 -> nums[2] 即 2 -> 4
3 -> nums[3] 即 3 -> 2
4 -> nums[4] 即 4 -> 2

我们可以画出这个“链表”的结构：

0 -> 1 -> 3 -> 2 -> 4
             ^     |
             |-----|

我们发现，索引 3 和 4 都指向了索引 2，形成了一个环的入口。这个重复的指向 2 正是因为 nums 数组中出现了重复的数字 2。因此，寻找重复数的问题就转化为了寻找链表环的入口问题。

寻找环的入口，最经典的算法就是 Floyd 判圈算法，也就是我们常说的“快慢指针”。

算法步骤

第一阶段：找到相遇点
- 定义两个指针，slow 和 fast，都从索引 0 开始。
- slow 每次走一步：slow = nums[slow]。
- fast 每次走两步：fast = nums[nums[fast]]。
- 由于链表中存在环，fast 指针最终会在环内追上 slow 指针。我们循环直到 slow == fast，这个相遇点在环内。
第二阶段：找到环的入口
- 将其中一个指针（例如 slow）重新放回起点，即 slow = 0。
- 另一个指针 fast 保持在相遇点不动。
- 现在，两个指针都每次走一步：slow = nums[slow]，fast = nums[fast]。
- 它们下一次相遇的点，就是环的入口，也就是我们要找的重复数。

为什么第二次相遇就是环的入口？

这是一个数学证明：

设链表起点到环入口的距离为 a。
环的长度为 b。
快慢指针在环内相遇时，慢指针走了 s 步，快指针走了 2s 步。
相遇点距离环入口的距离为 x。

那么：

慢指针走过的路程：s = a + x
快指针走过的路程：2s = a + n*b + x (快指针可能在环里绕了 n 圈)

将 s 代入第二个式子： 2(a + x) = a + n*b + x2a + 2x = a + n*b + xa + x = n*ba = n*b - x

这个公式 a = n*b - x 的含义是：

从链表起点到环入口的距离 a
等于从相遇点出发，走 n*b - x 的距离。
n*b 意味着在环里绕 n 圈，位置不变。-x 意味着从相遇点往回走 x 步，正好就是环的入口。

所以，当一个指针从起点出发，另一个指针从相遇点出发，它们最终会在环的入口相遇。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n + 1];  // 题目说明数组长度为 n+1

        // 读取数组元素
        for (int i = 0; i <= n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.findDuplicate(nums);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;

        // 第一阶段：找到相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 第二阶段：找到环的入口
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow; // 或者 return fast，此时它们相等
    }
}

复杂度分析

时间复杂度：O(n)
- 第一阶段，快指针在追上慢指针之前，走的步数不会超过链表长度 n。
- 第二阶段，两个指针分别从起点和相遇点出发，相遇时走的步数也不会超过 n。
- 因此，总的时间复杂度是线性的。
空间复杂度：O(1)
- 我们只使用了 slow 和 fast 两个指针，是常量级的额外空间。
抽象成环形链表II 快慢指针找到入口