随笔-寻找重复数（快慢指针，二分查找）.md

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

示例 1:

输入: [1,3,4,2,2] 输出: 2 示例 2:

输入: [3,1,3,4,2] 输出: 3 说明：

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

方法一：快慢指针

思路：采用的是链表是否有环的思路，由题可得，数组的元素有n+1; 数组中元素的大小为1-n； 并且其中必定存在重复元素，我们将nums[] 元素的值作为下次的指针，因为至少有两个重复元素，所以第二次出现的重复元素肯定会跳到第一次出现时，以它的值作为指针的下一位，这样就构成一个环；那么我们可以设置快慢指针，当进入环后，他们总会相遇； 具体的判断请参考 单链表

class Solution {
    public int findDuplicate(int[] nums) {
        int fast=0;
        int slow=0;
        while(true){
            slow=nums[slow];
            fast=nums[nums[fast]];
            if(fast==slow){
                slow=0;
                break;
            }
        }
        while(true){
            fast=nums[fast];
            slow=nums[slow];
            if(fast==slow){
                return fast;
            }
        }
   
    }
}

方法二：二分查找

思路：由题可知，当我们找到mid ，然后遍历整个数组，将数组中小于等于mid的元素记为count ，如果count>mid 那么重复元素就在l-mid之间，反之就在mid-r； 其实原理就是对数组进行排序，如果不重复，count肯定是小于或者等于mid的；

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