鞍山网站哪家好,网站白名单查询,网站建设自学 优帮云,wordpress建站要钱么leetcode习题287 Find the Duplicate Number 在答案中看到了floyd’s tortoise and hare 算法#xff0c;知道了如果有限状态机、迭代函数或者链表存在环#xff0c;那么是需要算法检测环是否存在。检测算法有三种:Floyd龟兔算法、Brent算法、Gosper算法。
Floyd龟兔算法
算…leetcode习题287 Find the Duplicate Number 在答案中看到了floyd’s tortoise and hare 算法知道了如果有限状态机、迭代函数或者链表存在环那么是需要算法检测环是否存在。检测算法有三种:Floyd龟兔算法、Brent算法、Gosper算法。
Floyd龟兔算法
算法描述
Floyd龟兔算法是一种指针算法。该算法仅使用移动速度不同的两个指针就能检测出是否有环。Floyd龟兔算法解决以下问题1检测是否有环。2环的起点节点。3环的长度。 1 检测是否有环。 想象在一个环形跑道上跑步两个人同时出发出发以后速度快的人终究会在某一点和速度慢的人相遇。一般这个时候相遇速度快的人比速度慢的人至少多跑一圈。 我们假设列表的开始节点是S环上的起始节点是P第一次相遇的节点是M。S和P的距离是p从P和M的距离是m,从M到p的距离是n。指针t和h初始状态下都指向S。接着t每次只有1步h每次走2步。只要二者没有相遇就一直按着这个速度走下去。当h无法前进到达队列末尾的时候可以判断没有环。如果t和h在某点再次相遇则确定有环。 举一个迭代函数的例子。有函数f定义域和值域都是 S {0,1,2,3,4,5,6,7,8}从x02x_02x02开始不断重复调用f能够产生一个序列2,0,6,3,1,6,3,1,6,3,1…产生了一个环6,3,1。 定义S是一个有限集合f是一个函数从S到S的一个映射x0x_0x0可以是S中的任意一个元素。对于任意的i0i0i0xif(xi−1)x_if(x_{i-1})xif(xi−1)。μ\muμ是换上的起点节点的最小下标λ\lambdaλ是环的长度。一定有xμxλμx_\mux_{\lambda\mu}xμxλμ 证明如果有环存在则对于任意的整数iμi\muiμ并且k0k0k0都有xixikλx_ix_{ik\lambda}xixikλ。对于特定的k来讲一定存在使得ikλik\lambdaikλ那这时候xix2ix_ix_{2i}xix2i。至此说明了速度不同的两个指针可以在某点相遇。
2 计算环长度 当t和h相遇在M点。因为相遇的点一定在环上。这时候保存h不动t按之前的速度继续前进直到和h再次相遇这个过程中移动的步数就是环的长度。
3 环的起始节点确定 在确定是否有环的过程中h走的距离是t走的距离的2倍。c为环长。t走的距离是 s1pma∗cs1pma*cs1pma∗ch走的距离是2∗s1pmb∗c2*s1pmb*c2∗s1pmb∗c,两式子相减得到s1(b−a)∗cpma∗cs1(b-a)*cpma*cs1(b−a)∗cpma∗c,得到pm环的整数倍。 为了找到环的起点t回到起点h在当前位置。同时向前他们再次相遇一定在P点。为什么呢因为从S到P的距离是p从P到M的距离是m因为mp是环长的整数倍所以当h走过距离p的时候也一定达到了P点。
算法时间复杂度令S到P的距离为m环的长度为n时间复杂度O(mn)O(mn)O(mn)。 空间复杂度O(1)。
参考 网页1 网页2 网页3
