Java第88题：模拟约瑟夫环：n 人报数 m 出列

题目

模拟约瑟夫环（数组或链表）：n 人报数 m 出列

思路

本题模拟约瑟夫环（数组或链表）：n 人围圈报数 m，第 m 个出列，直到剩一人或输出出列顺序。 可用数组标记存活或链表模拟；从当前位置数 m 个活人，出局后继续从下一位报数，直到满足题面停止条件。

解题分析

约瑟夫环（数组或链表）模拟：数组标记是否出局，从当前位置报数到 m 的出局，下一位继续，直到剩 0 人。n、m 不大时 O(n²) 模拟足够；n 很大时有递推公式 O(n)，但理解成本高，练手先用模拟。

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 5, m = 2;
        boolean[] alive = new boolean[n];
        Arrays.fill(alive, true);
        int left = n, i = 0, cnt = 0;
        while (left > 0) {
            if (alive[i]) {
                cnt++;
                if (cnt == m) {
                    System.out.print((i + 1) + " ");
                    alive[i] = false; left--; cnt = 0;
                }
            }
            i = (i + 1) % n;
        }
        System.out.println();
    }
}

运行示例

输出：

2 4 1 5 3