java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
解题思路 |
---|
弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤
- 判断是否有环,并得到快慢指针相遇的结点:慢指针每次走一格,快指针每次走两格,只要有环,必然会相遇。
- 获取构成环的结点:相遇后,让慢指针归0,快指针继续呆在相遇的地方,然后两个人依次一格一格的后移,最终再次相遇的地方,就是构成环的地方。
本题是数组题,如何想到用环形链表的解法呢? |
---|
- 首先,这个题的数组,下标范围和取值范围是几乎相同的。因为下标范围在0 ~ n。取值范围是1 ~ n。那么下标和元素值是可以联立的。我们可以设置链表结点为[下标,元素值]来构成链表。因为有重复的元素值,那么这个链表比如有环,图解如下:
![]()
- 既然抽象出了链表,就可以使用弗洛伊德判圈法,先判断是否有环,然后获取相遇结点位置。下面给出两个例子
文章来源:https://www.toymoban.com/news/detail-821993.html
- 获取了相遇结点后,接下来就是慢指针归0,快指针继续在相遇的结点。然后两个指针依次一格一格的后移即可。图解如下
![]()
代码:时间复杂度O(n) 空间复杂度O(1) |
---|
文章来源地址https://www.toymoban.com/news/detail-821993.html
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;//快慢指针
//将数组转换为链表,nums数组下标作为链表结点。对应下标的元素值作为指向下一个结点的指针
//因此,只要数组中有重复元素,那么这个链表一定有环
do{
slow = nums[slow];//相当于 slow = slow.next
fast = nums[nums[fast]];//相当于fast = fast.next.next;
}while(slow != fast);//找到环,并指向相遇结点
//然后slow归0,fast不变,依次后移,找到构成环的结点
slow = 0;//slow归0
while(slow != fast){//一格一格的后移,直到再次相遇,就是环的入口
slow = nums[slow];
fast = nums[fast];
}
return slow;//最终返回这个结点值
}
}
到了这里,关于java数据结构与算法刷题-----LeetCode287. 寻找重复数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!