弗洛伊德龟兔赛跑算法(弗洛伊德判圈算法)

弗洛伊德( 罗伯特・弗洛伊德)判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。

昨晚刷到一个视频，来自油管的Joma Tech，视频本身挺有意思的，当然这哥们也很有意思，经常在油管发视频然后在FB就被辞职了，现就职于谷歌。

里面介绍了如何实现下面这个的算法，主要是视频内容很有意思，当然这里还是介绍里面出现的几个算法。

题目：找出数组中的重复数字，数组里只有一个重复的数字，可以重复多次。其中算法的要求是时间复杂度小于O(n²)，空间复杂度是O(1)

题目是很简单，求解的办法也很多，有直接循环查找，为了提高效率还可以使用二分查找，视频中的前两个方法如下：

排序之后，相邻元素如果是相等即为重复数字。但运行的时间复杂度高，比较耗时。不能通过！

def findDuplicate1(nums):nums.sort()for i in range(1,len(nums)):if nums[i]==nums[i-1]:return nums[i]arr1=[1,3,4,2,2]
arr2=[8,1,3,4,2,4,5,4]print(findDuplicate1(arr1))#2
print(findDuplicate1(arr2))#4

使用字典或set来保存遍历数组里的值，然后判断是否已添加，如果有添加就说明是重复数值了。

这个虽然相较于上面的方法，时间缩短了，但是空间复杂度上来了，比较耗内存。不能通过！

def findDuplicate2(nums):seen={}for num in nums:if num in seen:return numseen[num]=Trueprint(findDuplicate2(arr1))#2
print(findDuplicate2(arr2))#4#或者set()也可以
def findDuplicate2_(nums):seen=set()for num in nums:if num in seen:return numseen.add(num)
print(findDuplicate2_(arr1))#2
print(findDuplicate2_(arr2))#4

接下来看下符合要求的算法，也就是下面介绍的龟兔算法。

当然这个题目还有一个限定条件，给定一个包含n + 1个整数的数组nums，其中每个整数都在1到n之间(包括)，不然我给出的示例就会出现索引越界了，这样就可以使用这个龟兔赛跑的算法，也有人管叫快慢指针，有重复就形成闭环：

def findDuplicate_ok(nums):tortoise=nums[0]hare=nums[0]while True:tortoise=nums[tortoise]#龟hare=nums[nums[hare]]#兔if tortoise==hare:breakptr1=nums[0]ptr2=tortoisewhile ptr1!=ptr2:ptr1=nums[ptr1]ptr2=nums[ptr2]return ptr1arr1=[1,3,4,2,2]
arr3=[1,4,6,8,2,3,8,5,7]
print(findDuplicate_ok(arr1))#2
print(findDuplicate_ok(arr3))#8

时间复杂度：O(n)，空间复杂度：O(1)

当然如果是初学者，会感觉到有点复杂，没关系，我们可以在龟(或兔或两者)的位置设置断点，然后步进，一步一步的看整个算法的执行流程就明白了，这个也是大家在需要进行调试或者了解一些变量的变化的最常见有效的方法。

不便调试的，我也将整个执行过程贴出来，方便观察：

数组：nums=[1,4,6,8,2,3,8,5,7]

	第1次	第2次	第3次	第4次	第5次
龟	nums[0]=1	nums[1]=4	nums[4]=2	nums[2]=6	nums[6]=8
兔	nums[0]=1	nums[nums[1]]=2	nums[nums[2]]=8	nums[7]=5	nums[3]=8

当迭代到第5次的时候，两者相等了，于是就跳出循环，然后就通过指针找出重复的值

ptr1=1	nums[1]=4	nums[4]=2	nums[2]=6	nums[6]=8
ptr2=8	nums[8]=7	nums[7]=5	nums[5]=3	nums[3]=8