题目描述

blablabla

样例

blablabla

算法1

(追击) $O(n)$

前面也有一篇O(n)的做法, 但是证明不太正确

首先题目是必定存在环, 每个位置的$i$指向$a_i$

也就是 $0->a[0]->a[a[0]]->…->x->a[x]->a[a[x]]->..->a[x]$

我们从$x$这个位置进入环$a[x]$, 能形成环, 在环内必然存某个位置$j, a[j]->a[x]$

故现在存在两个位置都指向$a[x]$ 故$a_x和a_j$相同, 都指向位置$a[x]$

设两个快慢指针$x, y$, 当相遇时为$a[x]$这个位置偏移$d$步, 设链长为$n$, 环长$m$, 则

$S_x = n + k_x \times m + d, S_y = n + k_y \times m + d$

且$S_x = 2 \times S_y$, 则

$(k_x - k_y) \times m = n + d$, 因为快指针速度时慢指针的两倍

当慢指针走完一圈, 快指针走完两圈, 级快指针必能在慢指针走完一圈之内追上慢指针(但我们并不知道$k_x - k_y$)

然后我们再把快指针$x$放回远点, 再次追击(这次两个指针速度都为1), 当快指针走到环的入口时$S_x = n$

$S_x^, = n, S_y^, = n + S_y = n + k_y \times m + n + d$

别忘了 $(k_x - k_y) \times m = n + d$

故 $S_y^, = n + k_x \times m$ 即当$x$刚入环的时候2者相遇, 此位置即是$a[x]$

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int x = 0, y = 0;
        for (; !x || (x ^ y); x = nums[nums[x]], y = nums[y]);
        for (x = 0; x ^ y; x = nums[x], y = nums[y]);
        return x;
    }
};