每日算法 — 使用java实现寻找重复数：Floyd判圈算法与快慢指针检测

算法背景

给定一个包含 n+1 个整数的数组，其中每个整数都在 1 到 n 之间（包含1和n），假设只有一个重复的整数，找出这个重复的数。这道题是LeetCode 287题，表面上是简单的查找问题，但优秀的解法需要将其转化为链表判环问题，运用Floyd判圈算法（龟兔赛跑算法）在O(n)时间、O(1)空间内解决。

这道题的精妙之处在于：将数组下标和值看作指针关系，从而构建出一个必然存在环的隐式链表。这种将数组问题转化为图论问题的思想，在算法设计中非常有价值。

核心思路

关键转化：将数组 nums 看作一个函数图（functional graph），其中 i -> nums[i] 表示一条有向边。

由于数组有n+1个元素，值域是[1,n]，从任意位置出发沿着 nums[i] 走，最终必然会进入环。因为有n+1个节点但只有n个不同的值，根据鸽巢原理，至少有一个值被访问两次，形成环。

Floyd判圈算法：
1. 找相遇点：慢指针每次走1步，快指针每次走2步，两者必然在环内某点相遇。
2. 找环入口：将一个指针重置到起点，两指针都以速度1前进，再次相遇点即为环入口（也就是重复数字）。

数学证明：设环前长度为a，环长为c，相遇时慢指针走了a+b步，快指针走了a+b+kc步。由于快指针速度是2倍，有2(a+b) = a+b+kc，即a+b = kc。将慢指针重置到起点走a步到达入口，相遇点再走c-b步也到达入口，而a = kc-b，所以两者同时到达入口。

完整Java实现

/**
 * 寻找重复数 - Floyd判圈算法（龟兔赛跑）
 * 时间复杂度: O(n)  空间复杂度: O(1)
 */
public class FindDuplicateNumber {

    /**
     * 核心算法：Floyd判圈
     * 将数组视为隐式链表，利用快慢指针找环入口
     */
    public int findDuplicate(int[] nums) {
        // 阶段1: 快慢指针找相遇点
        int slow = nums[0];
        int fast = nums[nums[0]];

        while (slow != fast) {
            slow = nums[slow];        // 慢指针走一步
            fast = nums[nums[fast]];  // 快指针走两步
        }

        // 阶段2: 找环入口（重复数字）
        int ptr1 = 0;       // 从起点出发
        int ptr2 = slow;    // 从相遇点出发

        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }

        return ptr1;
    }

    /**
     * 二分搜索解法 - 不修改数组的替代方案
     * 时间复杂度: O(n log n)  空间复杂度: O(1)
     */
    public int findDuplicateBinarySearch(int[] nums) {
        int left = 1, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 统计 <= mid 的数字个数
            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }

            // 如果count > mid，说明重复数字在[left, mid]中
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    /**
     * 位运算解法 - 利用二进制统计
     * 时间复杂度: O(n log n)  空间复杂度: O(1)
     */
    public int findDuplicateBit(int[] nums) {
        int n = nums.length - 1;
        int result = 0;

        // 对每一位分别统计
        for (int bit = 0; bit < 32; bit++) {
            int mask = 1 << bit;
            int countNums = 0, countRange = 0;

            for (int num : nums) {
                if ((num & mask) != 0) countNums++;
            }
            for (int i = 1; i <= n; i++) {
                if ((i & mask) != 0) countRange++;
            }

            // 如果该位在数组中出现次数多于正常范围，重复数该位为1
            if (countNums > countRange) {
                result |= mask;
            }
        }

        return result;
    }

    /**
     * 通用版本：寻找链表中环的入口节点
     * 经典Floyd判圈在链表中的应用
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // 找相遇点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }

        if (fast == null || fast.next == null) return null; // 无环

        // 找入口
        ListNode ptr = head;
        while (ptr != slow) {
            ptr = ptr.next;
            slow = slow.next;
        }
        return ptr;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        FindDuplicateNumber solution = new FindDuplicateNumber();

        // 测试用例1: 基本场景
        int[] nums1 = {1, 3, 4, 2, 2};
        System.out.println("数组: [1,3,4,2,2], 重复数: " + solution.findDuplicate(nums1));

        // 测试用例2: 重复数为1
        int[] nums2 = {1, 1, 2};
        System.out.println("数组: [1,1,2], 重复数: " + solution.findDuplicate(nums2));

        // 测试用例3: 较大数组
        int[] nums3 = {3, 1, 3, 4, 2};
        System.out.println("数组: [3,1,3,4,2], 重复数: " + solution.findDuplicate(nums3));

        // 对比三种解法
        System.out.println("\n--- 不同解法对比 ---");
        int[] test = {1, 4, 4, 2, 4};
        System.out.println("Floyd判圈: " + solution.findDuplicate(test.clone()));
        System.out.println("二分搜索: " + solution.findDuplicateBinarySearch(test.clone()));
        System.out.println("位运算: " + solution.findDuplicateBit(test.clone()));
    }
}

复杂度分析

扩展思考

1. 寻找缺失数字：如果数组有n个元素，值域[0,n]，找出缺失的那个数。可以用数学求和法：期望和 – 实际和。
2. 寻找两个重复数字：如果数组有n+2个元素，有两个重复数字，能否用Floyd判圈？可以，但需要更复杂的处理，通常使用异或或分桶法。
3. 循环检测的通用性：Floyd判圈不仅适用于链表和数组，任何可以定义”下一步”函数的结构都可以应用。