求解思路
这道题利用快慢指针的思想。
可以把数组看作一个特殊的链表,数组的值就是指向下一个节点的索引。比如 nums[0] = 3,就表示从索引 0 跳到索引 3。
因为数组中有重复数字,所以必然会形成一个环,就像链表有环一样。
我们的目标就是找到这个环的入口位置,而这个位置对应的数字就是重复的数字。
整个算法分2步走:
第1步用快慢指针找到环内的相遇点,慢指针每次走一步,快指针每次走两步,它们最终会在环内某处相遇;
第2步让快指针回到起点,然后两个指针都以相同速度(每次一步)前进,它们再次相遇的地方就是环的入口,也就是我们要找的重复数字。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static int findDuplicate(int[] nums) {
if (nums == null || nums.length < 2) {
return -1;
}
// 第1步:快慢指针找相遇点
int slow = nums[0];
int fast = 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];
}
return slow; // 返回重复的数字
}
|
如果觉得有帮助，欢迎点赞、关注、转发~