【leetcode】287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

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

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

示例 1：

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

这一题的思路是 41. 缺失的第一个正数 + 142. 环形链表 Ⅱ，也就是安排每个数字应该在的位置，并把他们看成一个链表，最后找到链表的起始节点。

如果我们把 一个数字 x 放在 数组 index x de位置，那么多余的一个数字只能放在 index 0 的位置上，也就是说如果我们从 index 0 开始，找 index 0 这个位置上的数字应该放在哪里，然后以此类推，一定能够形成一个 当前 数组 value 代表当前链表节点指向 下一个 index 的 链表，并且这个链表一定是成环的。

举一个 [4, 4, 1, 2, 3] 的例子

最终会形成这样的一个链表，此时，我们再用 142 的 快慢指针去寻找 链表的起始节点即可，他的 index 就是 答案

class Solution {
    public int findDuplicate(int[] nums) {
        // 等价于 寻找循环节 前的一个节点
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        } while(slow != fast);

        fast = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19