寻找重复数

leetCode-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

自己的思路，通过原地哈希的算法进行，但之后读题才发现，不能修改原数组。。

代码为：

class Solution {
    public static int findDuplicate(int[] nums) {
        for (int i = 0;i<nums.length;i++){
            while (nums[i]!=i+1){
                if (nums[i]==nums[nums[i]-1]) return nums[i];
                int a = nums[i];
                nums[i] = nums[nums[i]-1];
                nums[a-1] = a;
            }
        }
        return -1;
    }
}

解法2

通过二分法，因为题目中所给数组的范围在[1,n]之间，数量为n+1，因为有一个数重复。

因此，我们用二分方法可以通过数字出现的次数进行二分。

例如，这个没有重复的数组[1,2,3,4]：

则<=1的数只有一个，<=2的数只有两个，<=3的数只有三个，<=4的数只有四个

则如果下面这个有重复数字的数组为：[1,3,4,2,2]

若<=1的数只有一个，说明重复的数在1右侧，反之说明重复的数在1左侧，
若<=2的数只有两个，说明重复的数在2右侧，反之说明重复的数在2左侧
若<=3的数只有三个，说明重复的数在3右侧，反之说明重复的数在3左侧
若<=4的数只有四个，说明重复的数在4右侧，反之说明重复的数在4左侧

因为如果小于某一个数的数量大于这个数，就说明重复数一定出现在小于等于这个数的数字中。因此就可以使用二分法来控制搜索的范围，是在mid的前面（也就是小于等于该数）还是后面

代码为

class Solution {
    public static int findDuplicate(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while (l<r){
            int mid = (l+r)/2;
            int count = 0;
            for (int i =0;i<nums.length;i++){
                if (nums[i]<=mid) count++;
            }
            if (count>mid) r = mid;
            else l = mid+1;
        }
        return l;
    }
}

解法3

通过快慢指针的算法，如果数组中出现重复数字，通过索引指向的数字去找下一个索引的数，可以看作是一个循环链表。

如果没有重复的数组：[1,2,3,4]

0->1
1->3
2->4
3->2
我们从下标为 0 出发，根据 f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。这样可以产生一个类似链表一样的序列。
0->1->3->2->4->null

如果有重复数字的数组：[1,3,4,2,2]

其映射关系 n->f(n) 为：
0->1
1->3
2->4
3->2
4->2

以此类推产生一个类似链表一样的序列。
0->1->3->2->4->2->4->2->……

可以抽象为下图：

综上
1.数组中有一个重复的整数 <==> 链表中存在环
2.找到数组中的重复整数 <==> 找到链表的环入口

因此：

题中慢指针走一步 slow = slow.next ==> 本题 slow = nums[slow]
题中快指针走两步 fast = fast.next.next ==> 本题 fast = nums[nums[fast]]

也就转化了，求循环链表中环的入口的做法一样。

（1）快慢指针走，如果相等则停止。

（2）快指针指向第一个，慢指针不动，两个指针一次走一步，相等为结果。

代码为：

class Solution {
    public static int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while (nums[slow]!=nums[fast]){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int p1 = 0;
        int p2 = slow;
        while (nums[p1]!=nums[p2]){
            p1 = nums[p1];
            p2 = nums[p2];
        }
        return nums[p1];
    }
}