Leetcode力扣287题:寻找重复数（二分法和Floyd判圈算法）

ゝ一纸荒年。 2023-02-13 03:17 18阅读 0赞

## 寻找重复数 ##

昨天刚刚做了剑指Offer的面试题03,今天遇到一个类似的题目,也是找重复的问题.

题目:

给定一个包含 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的数组来统计，这就代表昨天那个题里面的，解法一不行，用哈希表存储的方法二也不行。  
其次：时间复杂度小于O(n2)，所以昨天那个题的方法五暴力双循环不行。  
再者：不能修改原数组，所以昨天那个题里面的方法三排序，以及方法四原址哈希，都不行。  
那么还有什么办法？  
（我承认我看了评论和题解，我一开始真没办法）

### 一.借助二分法（有点绕） ###

首先，以前用二分查找的时候，在一个有序数组里面，找到 mid ，判断比结果大还是小，然后确定在左边还是右边继续进行二分查找，一个 while 循环，最终就可以以O(lgn)的时间复杂度得到结果。

这个题如果是对数组本身进行二分查找，显然是做不到的，因为数组的元素没有大小顺序，但是可以借助这个方法的思想。

一个重要的点是，在长度为n+1的数组里，数字的大小范围是 1到 n 。也就是数组下标范围是 0 到 n ，数字范围 1 到 n ，二分查找的数字范围和数组的下标范围是一样的。

###### 我们用例子1来看：\[1,3,4,2,2\] ######

假设我们要找的目的值是 ans 。

对于在满足条件的从 1 到 n 范围的一个数字 i 来说,小于等于 i 的数字个数记为count

1. 如果 i 的范围是从 1 到 ans-1，count 一定是 <= i 本身的，因为这些 i 都不是我们要的ans，他们没有在数组里重复出现。  
2. 等 i 是 ans 的时候， count 是 >ans 的。因为小于他的数字没有重复，一个萝卜一个坑，而他自身重复了2个及以上，那 count 就>ans了。(会不会有那种,由于小于ans的数字缺了很多个,导致这时仍然count<ans,答案是否定的,因为这道题限定的是只有一个重复数字)  
3. 这样继续往后，大于 ans 的任何一个数 i ，都会满足一样的　count>ans．

也就是说我们要找的是临界的那一个数ｉ，它是我们的答案。

对于例子1，小于等于1的数字有1个，小于等于2的有3个（count突然大于ans了，2就是答案），小于等于3的有4个，小于等于4的有5个。

###### 下面来看具体做法： ######

１．初始：借助我们前面所说．这个数组里面的数字和下标的特殊关系，用下标代表结果，我们用一个变量 **ans** ，开始的二分游标 **left** 就是 1，**right** 是 n,（0不在数组范围），算出 **mid** (再次强调,注意，此是 mid 是一个下标，同时是我们试错用的一个，ans的备选数字)。

２.进入循环：遍历整个 nums 数组,按照上面分析的思路,对于每一次计算结果 mid ,都要遍历一次 nums 数组,来统计小于他的数字的个数 **count** ．  
如果count<＝mid，就要重新计算 mid ,应该是在 1 到 n 的右半部分;  
如果count> mid，说明结果可能是 mid ,也可能是在 mid 左边,我们以防万一,先把 mid 赋值给 mid, 然后继续向左半部分进行新的 mid 的计算,用终止条件来判断是否此时的 mid 是答案.

３．终止条件：left>right.　这时显然是二分过程达到了临界值,因为只有上一次是count＞mid的时候才存储了 ans ,之后不论是不断的向右二分,到达临界值,还是又有向左二分,到达临界值,都保证了更新的ans是正确答案.

代码:

class Solution {
        
        public int findDuplicate(int[] nums) {
        
            //查找的左右边界，以及结果初始值
            int left=1,right=nums.length-1,ans=-1;
    
            while(left<=right){
        
                int mid=(left+right)>>1;
                int count=0;//每轮查找的统计变量
                for(int num: nums){
        
                    if(num<=mid){
        
                        count++;//注意判断条件是小于等于  
                    }
                }
                //判断应该继续向左还是右
                if(count<=mid){
        
                    left=mid+1;
                }else{
        
                    right=mid-1;
                    ans=mid;//更新ans,保证正确性
                }
            }
            return ans;
        }
    }

这个方法可以看到，在外圈while的循环次数应该是O（lgn）因为是二分，内圈每次统计的时间是O（n），所以总时间复杂度是O（nlgn）。空间复杂度是O（1）。

### 二．快慢双指针，利用Floyd判圈算法 ###

背景知识:Floyd判圈算法或者龟兔赛跑算法。

龟兔赛跑这件事，如果兔子速度是乌龟的2倍，在一个环形跑道比赛，
    兔子会在第二圈结束的时候追上乌龟。
    （显然会追上，速度2倍，距离一样，时间二分之一，等乌龟跑完一圈，兔子跑完两圈，正好相遇）

Floyd判圈算法可以用来解决判断链表有没有环，以及环的长度，环开始的起点这三个问题。里面就用一个slow的指针和一个2倍速的 fast 指针来模拟乌龟和兔子。

1.  第一个问题．直接判断会不会追上，也就是slow和fast会不会相遇，即得答案；
2.  第二个问题．环的长度，在追上之后，让他们继续在环里走，这就是一个纯在跑道上重新开始的龟兔赛跑，那么他们再一次相遇的时候，fast走过的路就是2倍slow的路，slow走过的路，或者fast减去slow走过的路，就是环的长度。
3.   第三个问题．环开始的起点。首先本身这个链表是一部分不循环，到后面开始循环的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]  
在上图中,我们最后要求的就是A点，S是链表头，A是环开始的点，B点是slow和fast的相遇点。  
Floyd算法的解决方案，就是在B点相遇之后，让slow重新回到S点，然后让 fast 继续从B点开始换速度，和slow一样都是一倍速.  
此时两者同时重新开始走，等到他们再次相遇的时候，得到的位置就是A点。  
为什么呢？

> 首先，我们把他们第一次相遇的时候的式子列出来。  
> 这个环的周长记为circle，
> 
> slow 走了的距离是：ds=m+a \* circle+n  
> fast 走的的距离是：df=2 \* ds=m++b \* circle+n  
> a 和 b 分别表示他们在环里走了几圈，是整数。
> 
> 两个式子做一个差，可以得到ds=(b-a) \* circle
> 
> 也就是说，slow 走过的距离 ds ，其实是整数倍的 circle ，也就是若干圈这个环。
> 
> 那么Floyd算法再一次进行的操作，slow重新从S开始，fast还从B点继续,这次速度一样。
> 
> 当 slow 走到A点的时候，距离是 m
> 
> 此时 fast 走的距离也是m，加上他本身就离A点有n的距离，那相对于A点他就是走了n+m
> 
> 上面已知ds=m+a \* circle+n是整数倍的 circle，那里面的m+n显然也是整数倍的circle。也就是说 fast 相对于A点也走了整数倍的圈，又回到了A点。
> 
> 所以他们俩又相遇了，且在环的入口处。

回到这个题目，链表里面存在重复的数字，我们用 i 这个指针指向 nums\[i\] 之后，用nums\[i\] 作为另一个指针，指向下一个nums\[nums\[i\]\] 就巧妙的创造出来一个链表，且链表一定存在环。（毕竟数字重复，那么总会有nums\[i\]指向的位置数字又指回到某个已经出现过的数字了），这样就可以按照Floyd算法找到对应的环的入口，也就是我们要求的重复数字了。

比如还是例1：\[1,3,4,2,2\]

nums\[4\]=2,nums\[2\]=4,这样的一个环就产生了。

按照Floyd算法的做法过程如下表。  
![在这里插入图片描述][20200527000317829.png]

class Solution {
        
        public int findDuplicate(int[] nums) {
        
            int slow=0,fast=0;
            //第一次遍历,让两者相遇
            do{
        
                slow=nums[slow];
                fast=nums[nums[fast]];
            }while(slow!=fast);
    
            slow=0;
    
            //第二次遍历,确定环的入口
            while(slow!=fast){
        
                slow=nums[slow];
                fast=nums[fast];
            }
            //注意最后的返回值,slow,而不是nums[slow]
            //因为迭代过程slow和fast每次都替代成了下一个值,同时进行是否相遇的判断
            //所以最后相等的时候也是值相等,返回slow也就返回的是值
            return slow;
        }
    }

这个方法的时间复杂度是O（n），因为Floyd判圈算法只需要线性时间在原数组里游走。空间复杂度为O（1）。  
执行时间0m，击败100%。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526235315835.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70
[20200527000317829.png]: https://img-blog.csdnimg.cn/20200527000317829.png