理解为什么弗洛伊德的龟兔赛跑算法在应用于整数数组时有效

Question

我试图解决这个 leetcode 问题 https://leetcode.com/problems/find-the-duplicate-number/ 使用我自己的龟兔算法实现，当给定以下整数数组时会导致无限循环：

[3,1,3,4,2]

只有通过我的算法进行追踪后，我才能看到慢跑者和快跑者永远不会同时取两个重复值。这是我的伪代码算法：

initialize fast and slow runners to 0

while(true)

   move fast runner two indices forward
   move slow runner one index forward

   if arr[fast] == arr[slow] and fast != slow
      return arr[fast] // this is the duplicate

现在，我敢肯定精通离散数学的人能够凭直觉知道这种方法不会导致正确的解决方案，而不必像我必须先通过示例进行追溯。

我可以做出哪些推论或观察来让我看到这个算法不会起作用？我想知道如何通过一系列逻辑语句直观地识别此逻辑中的缺陷。换句话说，为什么这两个跑步者永远找不到这个例子中的重复项？我感觉可能和计数有关，但是我没有很强的离散背景。

澄清一下，我查看了正确的实现方式，所以我知道解决它的正确方法是什么。我只是认为这种方式的工作方式与将其应用于链表太相似了，在链表中，您会将快跑者向上移动两个节点，将慢跑者向上移动一个节点。感谢您的帮助。

Answer 1

Floyd 的乌龟算法在您检测链表中的循环时有效。它依赖于如果两个指针以不同的速度移动，它们之间的差距将不断增加到一个极限，之后如果存在循环，它将被重置。
在这种情况下，该算法确实找到了一个循环，因为在一些迭代之后两个指针都收敛到索引 0。但是，您不想在这里检测循环；您正在尝试查找重复项。这就是为什么它会陷入无限递归：它旨在检测一个循环（它正确地做到了），但在其基本实现中不检测重复项。

澄清一下，这是在您的示例数组上创建的示例链表。

3 -> 1 -> 3 -> 4 -> 2
'--<----<----<----<-'

如果您运行弗洛伊德算法，您会发现循环将在索引 0 处检测到，因为两个指针都将在那里收敛。它的工作原理是检查 fast 和 slow 是否指向 相同的位置 而不是它们是否具有相同的节点值（fast==slow 不是与 fast.value==slow.value).

相同

您正在尝试通过比较节点上的值来检查重复项，并检查节点是否指向同一位置。这实际上是缺陷，因为 Floyd 算法会检查两个指针是否指向同一位置以检测循环。
您可以阅读 this simple, informative proof 以提高您对指针为什么会收敛的直觉。

Answer 2

这主意不错。这是 Python 中的一个实现：

class Solution:
    def findDuplicate(self, nums):
        slow, fast = 0, 0
        while True:
            slow = nums[nums[slow]]
            fast = nums[fast]
            if slow == fast:
                break

        fast = 0
        while True:
            slow, fast = nums[slow], nums[fast]
            if slow == fast:
                break
        return slow

我们也可以使用二进制搜索：

class Solution:
    def findDuplicate(self, nums):
        lo, hi = 0, len(nums) - 1
        mid = lo + (hi - lo) // 2
        while hi - lo > 1:
            count = 0
            for num in nums:
                if mid < num <= hi:
                    count += 1
            if count > hi - mid:
                lo = mid
            else:
                hi = mid
            mid = lo + (hi - lo) // 2
        return hi

在 C++ 中：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>


static const struct Solution {
    static const int findDuplicate(
        const std::vector<int>& nums
    ) {
        int slow = 0;
        int fast = 0;

        while (true) {
            slow = nums[nums[slow]];
            fast = nums[fast];

            if (slow == fast) {
                break;
            }
        }

        fast = 0;

        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

理解为什么弗洛伊德的龟兔赛跑算法在应用于整数数组时有效

Understanding why Floyd's tortoise and hare algorithm works when applied to an array of integers

algorithm

logic

discrete-mathematics