[数据结构与算法]算法——寻找重复的数

案例分析：

给定一个包含?n + 1 个整数的数组?nums，其数字都在 1 到 n?之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]

输出: 2

示例 2:

输入: [3,1,3,4,2]

输出: 3

说明：

1. 不能更改原数组（假设数组是只读的）。
2. 只能使用额外的 O(1) 的空间。
3. 时间复杂度小于 O(n2) 。
4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

方法一：利用hashmap的方法，进行遍历数组，统计数字出现的次数

使用hashMap的方法：遍历整个数组，统计每个数字出现的次数

    Map<Integer, Integer> countMap = new HashMap<>();
    for( Integer num : nums ){
        if( countMap.get(num) == null )
            countMap.put(num, 1);
        else
            return num;
    }
    return -1;

方法二：可以利用set进行保存，我们知道set集合是无序的且数据是不能够重复。

        Set<Integer> set=new HashSet<>();
        for (Integer num : nums) {
            if(set.contains(num)){
                return num;
            }else
                set.add(num);
        }
        return -1;

无论是方法一还是方法二，时间复杂度都是O（n），对数组进行了一次的遍历，查找的时间复杂度为O（1）。空间复杂度为O（n）。需要一个外部的存储HashMap或者是HashSet进行做额外的存储，不太满足题目当中的要求。需要进行改进的。

方法三：使用二分查找的方式：

? ? ? ?现在增加到了N+1个数，根据抽屉原理，肯定会有重复数。对于增加重复数的方式，整体应该有两种可能：

1. 如果重复数（比如叫做target）只出现两次，那么其实就是1~N所有数都出现了一次，然后再加一个target；
2. 如果重复数target出现多次，那在情况1的基础上，它每多出现一次，就会导致1~N中的其它数少一个

因为数字是在1到N之间的，

    int l = 1;
    int r = nums.length - 1;
    // 二分查找
    while (l <= r){
        int i = (l + r) / 2; 
        // 对当前i计算count[i]
        int count = 0;
        for( int j = 0; j < nums.length; j++ ){
            if (nums[j] <= i)
                count ++;
        }
        // 判断count[i]和i的大小关系
        if ( count <= i )
            l = i + 1; 
        else
            r = i; 
        // 找到target
        if (l == r)
            return l;
    }
    return -1;

1. 时间复杂度：O(nlog n)，其中 n 为nums[] 数组的长度。二分查找最多需要O(logn) 次，而每次判断count的时候需要O(n) 遍历 nums[] 数组求解小于等于 i 的数的个数，因此总时间复杂度为O(nlogn)。
2. 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

方法五：使用快慢指针

整体思路如下：

1. 第一阶段，寻找环中的节点
   1. 初始时，都指向链表第一个节点nums[0]；
   2. 慢指针每次走一步，快指针走两步；
   3. 如果有环，那么快指针一定会再次追上慢指针；相遇时，相遇节点必在环中
2. 第二阶段，寻找环的入口节点（重复的地址值）
   1. 重新定义两个指针，让before，after分别指向链表开始节点，相遇节点
   2. before与after相遇时，相遇点就是环的入口节点

第二次相遇时，应该有：

慢指针总路程 = 环外0到入口 + 环内入口到相遇点 (可能还有 + 环内m圈)

快指针总路程 = 环外0到入口 + 环内入口到相遇点 + 环内n圈

并且，快指针总路程是慢指针的2倍。所以：

环内n-m圈 = 环外0到入口 + 环内入口到相遇点。

把环内项移到同一边，就有：

环内相遇点到入口 + 环内n-m-1圈 = 环外0到入口

    public int findDuplicate(int []nums){
        int fast=0,low=0;
        //寻找链表中的环
        do{
            low=nums[low];
            fast=nums[nums[fast]];
        }while (fast!=low);

        //寻找链表中的入口节点
        int ptr1=0,ptr2=low;
        while (ptr1!=ptr2){
            ptr1=nums[ptr1];
            ptr2=nums[ptr2];
        }
        return ptr1;
    }

1. 时间复杂度：O(n)，不管是寻找环上的相遇点，还是环的入口，访问次数都不会超过数组长度。

????????空间复杂度：O(1)，我们只需要定义几个指针就可以了。

?