约瑟夫环用数组解决Java

约瑟夫环（Josephus Problem），也被称为环形数组求解者，是一个经典的计算机科学问题，通常用于教授递归和动态规划的概念。这个题目源于一个古老的罗马游戏，参与者按照特定顺序从圆圈中跳过，直到最后剩下的人。

在Java中，你可以通过创建一个数组并维护两个指针来解决这个问题。基本步骤如下：

1. 初始化：给定人数n、步长k和一个初始位置p（通常设置为0或1）。创建一个大小为n的数组，代表游戏参与者的位置，数组下标表示人编号。

2. 初始状态：将初始位置p的人设为“存活”，其余位置设为“已淘汰”。

3. 循环：开始循环，每次循环：
- 如果当前轮到的人在被淘汰之列，跳过这个人。
- 否则，将这个人标记为淘汰，并更新下一个活人的位置，即`(current_position + k) % n`，其中%n操作保证在数组范围内。

4. 终止条件：当只剩下一个人时，返回他的位置就是最终的答案。

public int josephus(int n, int k, int p) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
        array[i] = i;
    }
    array[p-1] = 0; // 标记起始位置

    for (int i = 1; array.length > 1; ) {
        if (array[i] == 0) { // 跳过淘汰者
            i = (i + k - 1) % array.length;
        } else {
            array[i] = 0; // 淘汰当前位置的人
            i = (i + 1) % array.length;
        }
    }

    return array[0] + 1; // 返回最终答案，加1是因为实际数组下标是从1开始的
}