AcWing 14. 不修改数组找出重复的数字 - O(n)解法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 14. 不修改数组找出重复的数字 - O(n)解法原题链接中等

作者：

ihac , 2019-03-22 22:25:44 , 所有人可见 , 阅读 7348

72

37

算法1

(模拟链表) $O(n)$

两点前置知识：
1. 如何判断链表是否存在环？
双指针，一快（每次跑两格）一慢（每次跑一格），从链表首部开始遍历，两个指针最终都会进入环内，由于快指针每次比慢指针多走一格，因此快指针一定能在环内追上慢指针。而如果链表没环，那么快慢指针不会相遇。
2. 对于有环的链表，如何找到环的起点？
基于第一点，快慢指针相遇时，我们可以证明相遇的点与环起点的距离，一定和链表首部与环起点的距离相等。见图：

我们可以将数组视为一个（或多个链表），每个元素都是一个节点，元素的下标代表节点地址，元素的值代表next指针，因此，重复的元素意味着两个节点的next指针一样，即指向同一个节点，因此存在环，且环的起点即重复的元素。

为了找到任意一个环的起点（重复元素），我们只需要拿到一个链表的首部，然后利用前置知识即可解决问题。显然，0一定是一个链表的首部，因为所有元素值的范围在1 - n-1之间，即没有节点指向0节点。

题解流程即为：从0开始，快慢指针分别以2、1的速度向前遍历，当它们相遇时，将快指针置为0，继续分别以1、1的速度向前遍历，当它们再次相遇时，此时它们的下标就是题解。

时间复杂度分析：慢指针每次走一格，刚好遍历到链表尾部（即环起点）处结束，因此复杂度为$O(n)$
空间复杂度分析：$O(1)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int f = 0, s = 0;
        while (f == 0 || f != s) {
            f = nums[nums[f]];
            s = nums[s];
        }

        f = 0;
        while (f != s) {
            f = nums[f];
            s = nums[s];
        }
        return s;
    }
};