当前位置： 面试刷题>> 循环数组中的环 (经典算法题500道)
### 完整题目描述
给定一个可能含有循环的数组（即数组中某个位置的元素指向数组中的另一个位置，形成一个环），你需要编写一个函数来检测数组中是否存在这样的环，并返回环的起始位置（即数组中第一个指向环中下一个元素的元素的位置）。如果数组中不存在环，则返回-1。
假设数组中的元素是整数，且元素的值在数组的索引范围内，即可以使用元素值作为索引来访问数组中的下一个元素。注意，数组中可能存在多个环，但只需返回第一个找到的环的起始位置即可。
### 示例
给定数组：`[2, -1, 1, 2, 5]`，其中索引从0开始。
- 元素2指向索引2（因为数组元素是2），
- 元素-1指向自身（或理解为无效，因为索引-1越界），
- 元素1指向索引1（形成自环），
- 元素2（再次遇到）指向索引5（但索引5越界，实际应视为无效），
- 元素5（假设存在，但在这个数组中不存在）如果指向数组中的某个有效位置，将形成环的一部分。
然而，根据题目描述，我们只需要关注非越界且实际能形成环的情况。在这个例子中，元素1形成了自环，所以返回1作为环的起始位置。
### PHP 示例代码
```php
function detectCycle($nums) {
$slow = $fast = 0;
do {
if (!isset($nums[$fast]) || !isset($nums[$nums[$fast]])) {
// 数组越界或无法继续追踪
return -1;
}
$slow = $nums[$slow];
$fast = $nums[$nums[$fast]];
if ($slow == $fast) {
break;
}
} while ($slow != $fast);
if ($slow == $nums[0]) {
// 如果快慢指针相遇在起点，说明没有环或只有一个自环的节点
return -1;
}
// 找到环的起点
$slow = 0;
while ($slow != $fast) {
$slow = $nums[$slow];
$fast = $nums[$fast];
}
return $slow;
}
// 示例用法
$nums = [2, -1, 1, 2, 5];
echo detectCycle($nums); // 输出 1
```
### Python 示例代码
```python
def detectCycle(nums):
slow, fast = 0, 0
while True:
if fast >= len(nums) or nums[fast] >= len(nums) or nums[nums[fast]] >= len(nums):
return -1
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
if slow == nums[0]:
return -1
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
# 示例用法
nums = [2, -1, 1, 2, 5]
print(detectCycle(nums)) # 输出 1
```
### JavaScript 示例代码
```javascript
function detectCycle(nums) {
let slow = 0, fast = 0;
do {
if (fast >= nums.length || nums[fast] >= nums.length || nums[nums[fast]] >= nums.length) {
return -1;
}
slow = nums[slow];
fast = nums[nums[fast]];
if (slow === fast) {
break;
}
} while (slow !== fast);
if (slow === nums[0]) {
return -1;
}
slow = 0;
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
// 示例用法
const nums = [2, -1, 1, 2, 5];
console.log(detectCycle(nums)); // 输出 1
```
码小课网站中有更多相关内容分享给大家学习，包括算法详解、面试技巧、编程实践等，欢迎访问。