如何用“龟兔赛跑“找出数组中的重复数？

求解思路

这道题利用快慢指针的思想。

可以把数组看作一个特殊的链表,数组的值就是指向下一个节点的索引。比如 nums[0] = 3,就表示从索引 0 跳到索引 3。

因为数组中有重复数字,所以必然会形成一个环,就像链表有环一样。

我们的目标就是找到这个环的入口位置,而这个位置对应的数字就是重复的数字。

整个算法分2步走:

第1步用快慢指针找到环内的相遇点,慢指针每次走一步,快指针每次走两步,它们最终会在环内某处相遇;

第2步让快指针回到起点,然后两个指针都以相同速度(每次一步)前进,它们再次相遇的地方就是环的入口,也就是我们要找的重复数字。

代码实现

publicstaticintfindDuplicate(int[]nums){if(nums==null||nums.length<2){return-1;}// 第1步:快慢指针找相遇点intslow=nums[0];intfast=nums[nums[0]];while(slow!=fast){slow=nums[slow];// 慢指针走一步fast=nums[nums[fast]];// 快指针走两步}// 第2步:找环的入口fast=0;// 快指针回到起点while(slow!=fast){fast=nums[fast];slow=nums[slow];}returnslow;// 返回重复的数字}

如果觉得有帮助，欢迎点赞、关注、转发~