leetcode刷题(剑指offer) 287.寻找重复数

287.寻找重复数

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

提示：

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

题解

本题要求是只能使用常量级的空间复杂度，由于题目中给出了条件nums中的长度有n + 1个数字，且数字只在1-n中，因此想到了建立映射关系。

首先举个例子，如果是一个没有重复数字出现的数组，3, 2, 4, 2, 1， 将n和num[n]建立映射关系。如下

0 -> 3
1 -> 2
2 -> 4
3 -> 2
4 -> 1
// 建立出来的链表结构如下
0 -> 3 -> 2 -> 4 -> 1 -> 2

可以看出，让出现具有重复的数值的时候，使用n, num[n]的映射关系，构建出来的链表会出现环，而环的入口即是重复的数字。

思考这题的时候，主要有以下几种情况的思考。

1. 第一种情况，是我的解题的时候出现的问题，就是会脑补出一些不存在的情况，数组一共有n+1个成员，每个成员的取值只能在[1, n]的范围内，因此不会出现n + 1， 比如说, 一个数组长度是5，那么这个数组的成员中就不会出现5这个数字，因此不会存在，下一个指针没有指向的情况。

2. 第二种情况，就是自成环的情况，比如说有这样的映射,存在num = {3, 1, 3, 3, 2}

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

   这种情况就是出现了两个环，1和1自己成环了，不过这种不要紧，因为1自己的这个环，并不会干扰重复元素3所在环的运算，从0出发的时候不会经过1，只当1不存在就好了。

3. 第三种情况，多个元素成首位相连的环，如num = {2, 3, 2, 1, 4}

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

   这种情况，是最烧我脑的情况，因为1和3只出现了一次，而且他们也成环了，这也使得我一度怀疑这个思路对不对。但是后来画图出来，再仔细屡屡还是可以发现，我们搜环是从下标0开始的，因为题目已经明确了取值是在[1, n]范围内的，因此，当我们从0开始出发的时候，并不会遇上自成环的情况，也不会遇上首位相连的情况，因为没有任何一个元素会等于0，因此也不会形成0的首位相连环，因此还是这个思路，找到入环的第一个节点，就是重复的数，像上述的情况，1-3, 4-4的环，我们可以直接忽略他们。

   说了这么多，可以得出结论就是，这个题可以当成链表的题来做哈哈。

   ---

   那么为了方便思考，我们将情况切换回第一个例子。

   如何找到链表的入环节点，这里是一个固定的套路，为什么这样子我也不知道，记得就好了。

   定义一个快指针(faster)和一个慢指针(slower)。所谓快指针就是移动的比较快的指针，比如我一开始指针在0的位置，我移动一次就可以移动到2，移动了两格，慢指针，就是移动一次就移动一格。

   如果链表种存在环的话，使用快慢指针，一直向前移动，总有一天，这两个指针，会在环上的某个节点处相遇。

   当两个指针相遇之后，再重新定义一个指针，在此我将其定义为origin，指向链表一开始的0位置，然后让这个指针和慢指针(slower)一样的移动速度移动，当这个origin和slower相遇的时候，他们相遇的节点，就是入环节点，就是这么神奇，别问我为什么。

   代码如下：

public class _287寻找重复数 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 4, 2, 2};
        System.out.println(findDuplicate(nums));
    }

    public static int findDuplicate(int[] nums) {
        // 判断特殊情况
        if (0 == nums.length) {
            return 0;
        }
        // 快指针
        // 确定快慢指针的初始位置
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            start = i;
            if (start != slowerNext(nums, start)) {
                break;
            }
        }
        int faster = fasterNext(nums, start);
        int slower = slowerNext(nums, start);
        int origin = start;
        while (faster != slower) {
            faster = fasterNext(nums, faster);
            slower = slowerNext(nums, slower);
        }
        // 寻找环的出口
        while (origin != slower) {
            origin = slowerNext(nums, origin);
            slower = slowerNext(nums, slower);
        }
        return origin;
    }


    public static int fasterNext(int[] nums, int index) {
        return next(nums, index, 2);
    }

    public static int slowerNext(int[] nums, int index) {
        return next(nums, index, 1);
    }
    public static int next(int[] nums, int index, int steps) {
        if (steps == 0) {
            return index;
        }
        return next(nums, nums[index], steps - 1);
    }

}