🕊︎ 278.寻找重复数

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

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

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

思路

基本思想

题目中说，一共有n+1个数，但是数字的范围为[1,n]。这是典型的鸽巢原理的题目，即使每个数字只出现一次，那么最后一定会多一个元素，这个元素就是重复的。这是最极端的情况，真实情况下，重复的元素可能不止重复一次，但是题目中又描述，只有一个重复的元素，说明就是这种最极端的情况

为了找到这个重复的元素，可以借鉴 环形链表II 的思想，先找到环，之后找到环的入口，这个入口就是重复的元素，为了找到环，需要使用快慢指针的思想。为了找到入口，需要从链表的起点和当前相遇的点开始向后走，二者再次相遇的地方就是环的入口，这是经过环形链表II中推导得到的。

但是上面的思想是链表中，本题中提供的是数组，所以需要将数组转换成链表，于是可以利用下标index和数值nums[index]之间的映射关系来构造一个链表

由于一共有n+1个数，所以数组元素下标的范围为[0~n]，而数组中的每一个元素的范围为[1~n]，这可以说明，可以直接建立映射，不用担心建立应设置后数组下标越界的情况

所以第一阶段就是判断环在哪

1
2
3
4
5
6
7
8
9

int slow = nums[0];
    int fast = nums[0];
	//快慢指针先各走一步
    slow = nums[slow];
    fast = nums[nums[fast]];
    while (slow != fast){//不用担心下标越界的情况
        slow = nums[slow];
        fast = nums[nums[fast]];
}

因为必须要先走一步，所以可以将while循环改成do while循环

1
2
3
4
5
6
7

int slow = nums[0];
int fast = nums[0];
//找到快慢指针的相遇点
do{
    slow = nums[slow];
    fast = nums[nums[fast]];
}while (slow != fast);

上面代码中的快慢指针移动的方式需要注意，slow = nums[slow]代表慢指针走了一步。fast = nums[nums[fast]]代表快指针走了两步。当退出循环的时候，就是找到环的时候，此时需要将环的入口找到

找入口的代码就是一个指针从起点出发，一个指针从相遇点出发，按照相同的步伐向后走。再次相遇就找到了环的入口，这个地方就是重复元素出现的位置

核心就是将数组转换成链表，利用了index和nums[index]之间的映射关系

执行流程

1. 利用下标和元素之间的映射关系将数组转换成链表，然后利用快慢指针找到环
2. 一个指针从起点出发，一个指针从相遇点出发，按照相同的步伐找到环的入口
3. 返回入口元素就是重复的元素

代码

根据以上分析，得出以下代码：

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

class Solution {
    //不能修改数组代表不能对数组排序
    //空间复杂度为O(1)代表不能使用容器或者辅助数组
    //第一种想法就是拿每一个元素去与剩下的元素匹配，但是超时了
    //借鉴环形链表的思想
    public int findDuplicate(int[] nums) {
       int slow = nums[0];
       int fast = nums[0];
       //找到快慢指针的相遇点
       do{
           slow = nums[slow];
           fast = nums[nums[fast]];
       }while (slow != fast);
       
       //找到环的入口
       fast = nums[0];
       while (slow != fast) {
           slow = nums[slow];
           fast = nums[fast];
       }
       //返回入口处的元素
       return slow;
    }
}

总结

重点或者说巧妙地地方就是将数组转换成链表，利用了下标和元素之间的对应关系，由于存在鸽巢原理的情况，所以一定有一个重复元素，并且按照题意只有唯一一个重复元素，利用环形链表II的思想，找到环之后，环的入口处就是重复元素，也就是最终的答案

1. 数组转换成链表
2. 找到环的入口
3. 返回结果