寻找重复数

题目要求

给定一个长度为 n + 1 的整数数组 nums，其中的数字都在闭区间 [1, n] 内。根据鸽巢原理，至少存在一个数字是重复的。题目的要求是找出这个重复的数字。

需要注意的是：

数组 nums 中只有一个数字重复，但它可能重复多次。
需要找出这个重复的数字。
在寻找这个数字的过程中，不允许修改原数组 nums。
解决方案中只能使用常量级别 O(1) 的额外空间。

解题思路

由于不能修改原数组且只能使用常量级别的额外空间，一些常规的排序或哈希表方法都不适用。这里可以使用一个类似于链表环路检测的方法——弗洛伊德的龟兔赛跑算法（Floyd's Tortoise and Hare Algorithm）。

初始化：设置两个指针，一个快指针（兔子）和一个慢指针（乌龟）。初始时，都位于数组的起始位置。
第一阶段：快指针每次移动两步，慢指针每次移动一步，直到它们在环内相遇。由于存在重复的数字，数组中的数字可以看作是指向下一个索引的指针，因此一定会形成一个环。
第二阶段：在快慢指针相遇后，将快指针重新置于起始位置，慢指针保持在相遇点。然后，两个指针都以相同的速度（每次移动一步）移动，当它们再次相遇时，相遇点就是重复数字的索引。

这个算法的关键在于理解数组中的数字可以表示为指向另一个索引的指针，从而将问题转化为链表环路检测问题。由于所有数字都在 [1, n] 范围内，所以数组中的每个数字都可以指向数组内的一个有效索引，这保证了环的存在。

Golang 版本

package main

func findDuplicate(nums []int) int {
    // 初始化快慢指针
    slow := nums[0]
    fast := nums[0]

    // 第一阶段：寻找快慢指针相遇点
    do {
        slow = nums[slow]
        fast = nums[nums[fast]]
    } while slow != fast

    // 第二阶段：重置快指针，寻找环的入口
    fast = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    // 返回重复的数字
    return slow
}

func main() {
    // 示例
    nums := []int{1, 3, 4, 2, 2}
    duplicate := findDuplicate(nums)
    println("The duplicate number is:", duplicate)
}

这段代码实现了上述描述的弗洛伊德的龟兔赛跑算法，用于在不修改原数组且只使用常量级额外空间的条件下找出重复的数字。在 main 函数中，给出了一个示例数组，并调用 findDuplicate 函数来找出并打印重复的数字。

C++版本

#include <iostream>
#include <vector>

class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        // 初始化快慢指针
        int slow = nums[0];
        int fast = nums[0];

        // 第一阶段：寻找快慢指针相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 第二阶段：重置快指针，寻找环的入口
        fast = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        // 返回重复的数字
        return slow;
    }
};

int main() {
    // 示例
    std::vector<int> nums = {1, 3, 4, 2, 2};
    Solution solution;
    int duplicate = solution.findDuplicate(nums);
    std::cout << "The duplicate number is: " << duplicate << std::endl;
    return 0;
}

这段 C++代码实现了弗洛伊德的龟兔赛跑算法，用于在不修改原数组且只使用常量级额外空间的条件下找出重复的数字。在 main 函数中，给出了一个示例数组，并调用 findDuplicate 函数来找出并打印重复的数字。

Python 版本

def findDuplicate(nums):
    # 初始化快慢指针
    slow = fast = nums[0]

    # 第一阶段：寻找快慢指针相遇点
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # 第二阶段：重置快指针，寻找环的入口
    fast = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    # 返回重复的数字
    return slow

# 示例
nums = [1, 3, 4, 2, 2]
duplicate = findDuplicate(nums)
print(f"The duplicate number is: {duplicate}")

这段 Python 代码同样实现了弗洛伊德的龟兔赛跑算法，用于在不修改原数组且只使用常量级额外空间的条件下找出重复的数字。在示例中，定义了一个数组 nums 并调用 findDuplicate 函数来找出并打印重复的数字。

Java 版本

public class Solution {
    public int findDuplicate(int[] nums) {
        // 初始化快慢指针
        int slow = nums[0];
        int fast = nums[0];

        // 第一阶段：寻找快慢指针相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 第二阶段：重置快指针，寻找环的入口
        fast = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        // 返回重复的数字
        return slow;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 3, 4, 2, 2};
        int duplicate = solution.findDuplicate(nums);
        System.out.println("The duplicate number is: " + duplicate);
    }
}

这段 Java 代码实现了弗洛伊德的龟兔赛跑算法，用于在不修改原数组且只使用常量级额外空间的条件下找出重复的数字。在 main 方法中，创建了一个示例数组并调用 findDuplicate 方法来找出并打印重复的数字。

Rust 版本

fn find_duplicate(nums: Vec<i32>) -> i32 {
    let mut slow = nums[0];
    let mut fast = nums[0];

    // 第一阶段：寻找快慢指针相遇点
    loop {
        slow = nums[slow as usize];
        fast = nums[nums[fast as usize] as usize];
        if slow == fast {
            break;
        }
    }

    // 第二阶段：重置快指针，寻找环的入口
    fast = nums[0];
    while slow != fast {
        slow = nums[slow as usize];
        fast = nums[fast as usize];
    }

    // 返回重复的数字
    slow
}

fn main() {
    let nums = vec![1, 3, 4, 2, 2];
    let duplicate = find_duplicate(nums);
    println!("The duplicate number is: {}", duplicate);
}

这段 Rust 代码实现了弗洛伊德的龟兔赛跑算法，用于在不修改原数组且只使用常量级额外空间的条件下找出重复的数字。在 main 函数中，定义了一个示例向量 nums 并调用 find_duplicate 函数来找出并打印重复的数字。

总结

上述解法基于弗洛伊德的龟兔赛跑算法（Floyd's Tortoise and Hare Algorithm），这是一种用于检测链表中环的存在的算法。在这个问题中，我们将数组视为一个隐式的链表，其中每个位置可以看作是链表的一个节点，节点的值指向下一个节点的索引。

解法的核心思想是使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。由于数组中有重复的数字，意味着至少有两个位置指向了同一个值，这就形成了一个环。按照以下步骤进行：

初始化：将两个指针都置于数组的起始位置。
第一阶段：移动快慢指针，直到它们相遇。由于快指针每次移动两步，慢指针每次移动一步，如果存在环，它们最终会在环内相遇。
第二阶段：将快指针重置回数组的起始位置，然后以相同的速度移动快慢指针（每次一步），当它们再次相遇时，相遇点即为环的入口，也就是重复的数字。

这种方法的优点是不需要修改原数组，也不需要使用额外的空间（除了两个指针变量），因此空间复杂度为 O(1)。时间复杂度为 O(n)，因为指针最多会遍历两次数组。

在实际代码实现中，需要注意的是数组索引和值的转换，特别是在像 Rust 这样的语言中，需要将整数值转换为 usize 类型以用作索引。此外，由于这种方法依赖于数组中的值作为索引，因此它特别适用于题目中给出的条件，即数组中的数字都在 1 到 n 的范围内。

hot-100