社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
题目描述：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内，找出数 组中任意一个重复的数字
思路：将数组的值看成链表，快慢指针
如图，数组 [11, 2, 5, 8, 6, 7, 2, 9, 4, 3, 1, 10]， 转化成链表，快慢指针分别为 slow 和 fast， 起初指向第一个点 11。之后快指针每次走2步，慢指针每次走1步。假设在环中 x处相遇，慢指针肯定没走完一圈，快指针必然走完了一个环，此时慢指针的路程为 a+x快指针为 a+x+y，快指针的路程是慢指针的2倍，所以得到，慢指针剩下再走 y-x = a 就走完一圈，此时将快指针从起点，每次一步走，慢指针继续一步一步走，最终必然在环的入口相遇，即为重复的数字
public int findDuplicate(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int slow = 0;
int fast = 0;
for (int i = 0; i < numbers.length; i++) {
slow = numbers[slow];
fast = numbers[numbers[fast]];
if (fast == slow) {
fast = 0;
while (fast != slow) {
fast = numbers[fast];
slow = numbers[slow];
}
return slow;
}
}
return -1;
}
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
