每日算法 — 使用java实现约瑟夫环：循环链表模拟与数学递推公式

引言

约瑟夫环（Josephus Problem）是计算机科学中最经典的算法问题之一，其历史可以追溯到公元1世纪。相传犹太历史学家弗拉维奥·约瑟夫斯与40名战友被罗马军队围困，他们决定宁死不屈，围成一圈，从某一人开始，每数到第三人便将其淘汰，直到最后只剩下约瑟夫斯和他的一位朋友。这个问题经过两千年的演变，已经成为数据结构、递归思维和数学递推的经典教学案例。

本文将用Java完整实现约瑟夫环问题，从直观的循环链表模拟，到优雅的数学递推公式，帮助读者在层层递进中理解算法优化的本质。

问题形式化描述

假设有 n 个人围成一圈，从第一个人开始报数，每数到 k 的人被淘汰出局，剩下的人继续从1开始报数，直到最后只剩下一人。求胜利者的初始编号（编号从0开始）。

示例

当 n = 5, k = 2 时，淘汰顺序为：1 → 3 → 0 → 4，最后剩下编号2的人获胜。

方法一：循环链表模拟

最直观的思路是用循环链表模拟整个淘汰过程。每个节点代表一个人，指针每移动 k-1 步就删除当前节点。

/**
 * 循环链表节点
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

/**
 * 使用循环链表模拟约瑟夫环
 * 时间复杂度：O(n × k)，每次删除需要移动k-1步
 * 空间复杂度：O(n)，需要存储n个节点
 */
public class JosephusLinkedList {

    public static int findSurvivor(int n, int k) {
        if (n <= 0 || k <= 0) return -1;

        // 构建循环链表: 0 -> 1 -> 2 -> ... -> n-1 -> 0
        ListNode head = new ListNode(0);
        ListNode current = head;
        for (int i = 1; i < n; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }
        current.next = head; // 首尾相连形成环

        ListNode prev = current; // prev始终指向current的前一个节点
        current = head;
        int remaining = n;

        // 模拟报数淘汰过程
        while (remaining > 1) {
            // 移动k-1步到达被淘汰节点
            for (int i = 0; i < k - 1; i++) {
                prev = current;
                current = current.next;
            }
            // 删除current节点
            prev.next = current.next;
            current = prev.next; // 从下一个节点重新开始报数
            remaining--;
        }

        return current.val;
    }

    public static void main(String[] args) {
        System.out.println(findSurvivor(5, 2));  // 输出: 2
        System.out.println(findSurvivor(7, 3));  // 输出: 3
        System.out.println(findSurvivor(10, 4)); // 输出: 4
    }
}

循环链表模拟的优点是思路清晰、过程直观，适合理解问题本质。但当 n 很大时，每次删除操作的时间开销会成为性能瓶颈。

方法二：数学递推公式

约瑟夫环存在一个优美的数学递推关系。设 f(n, k) 表示 n 个人、步长为 k 时胜利者的编号，则有如下递推式：

f(1, k) = 0                          // 只有1人时，编号0获胜
f(n, k) = (f(n-1, k) + k) % n        // n > 1 时的递推关系

递推公式的直观理解

当第一个人（编号为 (k-1) % n）被淘汰后，剩下 n-1 个人构成一个新的子问题。这个新子问题的解是 f(n-1, k)，但它是在重新编号后的坐标系中的结果。我们需要将这个结果映射回原始编号系，即加上 k 并对 n 取模。

/**
 * 递归实现约瑟夫环递推公式
 * 时间复杂度：O(n)，每层递归计算一次
 * 空间复杂度：O(n)，递归栈深度
 */
public class JosephusRecursive {

    public static int findSurvivor(int n, int k) {
        if (n <= 0 || k <= 0) return -1;
        return josephus(n, k);
    }

    private static int josephus(int n, int k) {
        if (n == 1) return 0;
        return (josephus(n - 1, k) + k) % n;
    }

    public static void main(String[] args) {
        System.out.println(findSurvivor(5, 2));  // 输出: 2
        System.out.println(findSurvivor(7, 3));  // 输出: 3
        System.out.println(findSurvivor(41, 3)); // 输出: 30 (约瑟夫斯原始问题)
    }
}

迭代优化：消除递归开销

递归实现虽然优雅，但 n 很大时会导致栈溢出。通过从底向上迭代计算，可以将空间复杂度优化到 O(1)：

/**
 * 迭代实现约瑟夫环递推公式
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)，仅使用常数额外空间
 */
public class JosephusIterative {

    public static int findSurvivor(int n, int k) {
        if (n <= 0 || k <= 0) return -1;

        int survivor = 0; // f(1, k) = 0

        // 从2人逐步递推到n人
        for (int i = 2; i <= n; i++) {
            survivor = (survivor + k) % i;
        }

        return survivor;
    }

    public static void main(String[] args) {
        System.out.println(findSurvivor(5, 2));      // 输出: 2
        System.out.println(findSurvivor(100, 7));    // 输出: 48
        System.out.println(findSurvivor(10000, 3));  // 输出: 3616
    }
}

方法三：数组模拟（空间优化版）

如果需要在不使用链表的前提下直观展示淘汰过程，可以用布尔数组标记存活状态：

/**
 * 使用数组标记存活状态模拟约瑟夫环
 * 时间复杂度：O(n × k)
 * 空间复杂度：O(n)
 * 适合需要输出完整淘汰顺序的场景
 */
public class JosephusArray {

    public static int findSurvivorWithOrder(int n, int k) {
        if (n <= 0 || k <= 0) return -1;

        boolean[] alive = new boolean[n];
        java.util.Arrays.fill(alive, true);

        int remaining = n;
        int index = 0; // 当前报数位置
        int count = 0; // 当前报数值

        System.out.print("淘汰顺序: ");

        while (remaining > 1) {
            if (alive[index]) {
                count++;
                if (count == k) {
                    alive[index] = false;
                    System.out.print(index + " ");
                    count = 0;
                    remaining--;
                }
            }
            index = (index + 1) % n; // 循环移动
        }

        // 找到最后幸存者
        for (int i = 0; i < n; i++) {
            if (alive[i]) {
                System.out.println("\n幸存者: " + i);
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        findSurvivorWithOrder(5, 2);
        // 输出: 淘汰顺序: 1 3 0 4
        //       幸存者: 2
    }
}

复杂度对比与选型建议

拓展：输出完整淘汰序列

在某些场景下，不仅需要知道最后的幸存者，还需要输出完整的淘汰顺序。基于数组标记法可以很容易地扩展这一功能，已在方法三中实现。如果 k = 2 的特殊情况，还可以利用位运算进一步优化到 O(1) 时间：当 k = 2 时，f(n, 2) = 2 * (n - 2^⌊log₂n⌋) + 1。

总结

约瑟夫环问题完美展现了算法优化的渐进过程：从直观模拟到数学抽象，从递归 elegance 到迭代 efficiency。循环链表模拟让初学者理解问题本质，数学递推公式揭示了问题背后的周期性规律，迭代实现则将时空复杂度降到最优。

掌握这道经典问题，不仅能加深对链表、递归和取模运算的理解，更能培养”从模拟到公式”的算法优化思维——这是解决更复杂组合数学问题的关键能力。