Josephus 问题是下面的游戏：
N个人编号从1到N，围坐成一个圆圈，从1号开始传递一个热土豆。经过M此传递之后拿着热土豆的人将被清除离座，围坐的圆圈紧缩，由坐在被清除人后面的人拿起热土豆继续游戏。最后剩下的人取胜，因此，如果 M=0 和 N=5，则游戏人依序被清除，5号游戏人获胜。如果 M=1和N=5，则清除的人的顺序是 2，4，1，5 。
a. 编写一个程序解决 M 和 N 在一般值下的 Josephus 问题，应使程序尽可能的高效率，要确保能够清除各个单元
b. 你的程序的运行时间是多少？
题干：
总共 N 个人，编号依次是 1 – N
从第1个人开始传递，传递 M 次后的人离座，每次清除的间隔是 M
元素清除后，下个元素作为起始重新计算间隔
第一版本
public static void josephus(int m, int n) {
LinkedList<Integer> indexList = new LinkedList<>();
for (int i = 1; i <= n; i++)
indexList.add(i);
int i = 0;
System.out.print("remove: ");
while (n > 0) {
// 每次计算出下一个要清除元素的位置,这里计算的时候如果超过了剩余人数，则直接从头开始，所以会做取余的操作
int rm = (i + m) % n;
// 删除一个元素直接，这个索引会被下一个元素占用，所以不需要 +1
i = rm;
n--; // 剩余人数 -1
System.out.print(indexList.remove(rm) + ", ");
}
System.out.println();
}
这里的基本思路就是，每次计算出下一个要清除元素的位置，然后调用List 的 remove 方法清除元素
外部循环的时间复杂度为 O(n)，remove操作的时间复杂度也是O(n)，因为线性表需要移动元素，链表需要移动指针，所以整个方法的时间复杂度应该是 O(n ^ 2)
移除步骤流程可以看下图
优化
1、 这里使用了LinkedList，主要考虑 ArrayList 跟 LinkedList 的下标删除的时间复杂度应该是一样的都是O(n)，但是实际测试 ArrayList 的下标删除会快很多，因为随着 N 的变大，大部分的删除都是在表的中间进行，ArrayList随机访问速度快，然后数组前移的速度会明显快过 LinkedList 的下标移动的过程，所以时间会快很多
测试 M = 50，N = 50000
时间可以从 1135 ms 降至 75 ms
2、 这里还有个地方感觉有优化的空间，即当每次移除的元素的时候，不一定都是从头开始查找的，当需要移除的元素没有从头再开始算，那么列表每次移除时不需要循环开始找的开销可以进行合并为一次遍历，压缩查找人员列表元素进行移除时的开销
参考答案的例子就是这种方案实现
参考答案
public static void josephus2(int m, int n) {
int i, j, mPrime, numLeft;
ArrayList<Integer> l = new ArrayList<>();
for (i = 1; i <= n; i++)
l.add(i);
ListIterator<Integer> iter = l.listIterator();
int item = 0;
numLeft = n;
System.out.print("remove: ");
for (i = 0; i < n; i++) {
mPrime = m % numLeft;
if (mPrime <= numLeft/2) {
if (iter.hasNext())
item = iter.next();
for (j = 0; j < mPrime; j++) {
if (!iter.hasNext())
iter = l.listIterator();
item = iter.next();
}
} else {
for (j = 0; j < numLeft-mPrime; j++) {
if (!iter.hasPrevious())
iter = l.listIterator(l.size());
item = iter.previous();
}
}
System.out.print(item + ", ");
iter.remove();
if (!iter.hasNext())
iter = l.listIterator();
numLeft--;
}
System.out.println();
}
这里有几个问题：
1、 针对多次不需要循环从头开始的操作，使用迭代器合并为一次遍历，这个优化针对 LinkedList 这种需要顺序访问，每次访问开销较大时具有优化价值，对于 ArrayList 这种随机访问，索引删除元素的开销都在移动元素上的数据结构，这个优化并没有左右
2、 这种方案还引入了一个新的问题，因为使用迭代器遍历，整体的时间复杂度我简单认为还是 O(n ^ 2), 但是当 M 取值较大时，这种算法优化的点反而成为性能的开销点，比如 M = 10000, N = 5000 时，第一种方案仍然是通过一次计算计算出需要删除的元素，而现在的方案则需要每次进行大量的移动操作，造成时间开销
所以第二种方案的性能并不稳定，受 M 值影响，M 决定这个算法每次移动的距离
最终方案
所以最终我觉得还是第一种方案，然后将 LinkedList 换为 ArrayList 的方案最优
这里有个前提，ArrayList 的索引删除比 LinkedList 的索引删除快很多，虽然按时间复杂度来将都是O(n)，但是实际平台对算法的优化不一样，还是会有比较大的差异
源码可以参考 数据结构与算法分析 java语言描述 学习与记录