1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| // @lc code=start
impl Solution {
/// ## 解题思路
/// - 快慢指针法
/// 1. 由于任意的 nums[i] in [1..n], 所以可以定义一种遍历方法：
/// 对于nums[i], 下一次遍历的下标 next_i = nums[i]
/// 那么，从起点i开始，可以遍历nums一系列的点，
/// 这些遍历过程就形成了一个有向链表；
/// 2. 由于nums.len() == n+1, 故从任何一个元素开始遍历，最后会形成环；
/// 3. 如果存在 `nums[i] == nums[j] (i != j)`,
/// 则有 `nums[nums[i]] == nums[nums[j]]`
/// 后续所有的遍历将合并为一条路径，即两条有向链表必然存在交叉点；
/// 4. 对于i=0，由于0不在[1..n]范围内，故从nums[0]开始遍历的路径存在一个中间交叉的环，
/// 遍历路径为6字型；
/// 5. 找到6字型的交叉点即为重复元素的值；
/// 6. 为寻找交叉点，可使用快慢指针法进行查找；
/// 7. 第一步,使用快慢指针, 查找环上的相遇点;
/// 8. 设0到交叉点的距离为a, 环的长度为b, 相遇时,slow指针移动的距离为s, fast指针移动的距离为f;
/// 因为fast指针的速度是slow指针的2倍, 所以: `f=2s`.
/// 另外,fast和slow相遇时, fast和slow的差一定是环长度的正整数倍,
/// 所以有 `f-s=kb`
/// 综合以上,可以得到: `s=kb`
/// 而从0开始,环的入口为`a+nb`, 相遇时,slow指针已经走了s=kb步,
/// 如果s再走a步, 即s+a=a+kb, 就回到环的入口.
/// 9. 所以,第二步,在快慢指针相遇后, 让fast回到0开始处, slow在相遇点,两者同时按相同的速度遍历
/// 则当a步后, 两者将在环入口相遇,此时交叉点即为重复值.
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
// slow,fast同时从nums[0]开始
let mut slow = 0;
let mut fast = 0;
// 通过快慢指针,计算环上的相遇点
loop {
slow = nums[slow] as usize; // s
fast = nums[nums[fast] as usize] as usize; // f = 2s
if slow == fast { //指针相遇, f-s=kb
break; //中断遍历
}
}
//将fast重新移动到0开始处,
//slow保持在相遇点位置
fast = 0 as usize;
while slow != fast { //两者同步向环相交点移动
slow = nums[slow] as usize;
fast = nums[fast] as usize;
}
fast as i32 //相交点为重复数
}
}
// @lc code=end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::find_duplicate(vec![1, 3, 4, 2, 2]), 2);
assert_eq!(Solution::find_duplicate(vec![3, 1, 3, 4, 2]), 3);
assert_eq!(Solution::find_duplicate(vec![2, 2, 2, 2]), 2);
}
}
|