什么是约瑟夫问题？ 

约瑟夫问题：n个人围成一圈，初始编号从1~n排列，从约定编号为x的人开始报数，数到第m个人出圈，接着又从1开始报数，报到第m个数的人又退出圈，以此类推，最后圈内只剩下一个人，这个人就是赢家，求出赢家的编号。

是不是有点点复杂，其实该问题归结为模拟类型的算法题，根据题目要求模拟即可。

我说，一行代码解决约瑟夫问题！

？？？我去

别着急，我们一步一步学习

在第一次遇到这个题的时候，我是用数组做的，我猜绝大多数人也都知道怎么做。方法是这样的：

用一个数组来存放 1，2，3 ... n 这 n 个编号，如图（这里我们假设n = 6, m = 3）

 然后不停着遍历数组，对于被选中的编号，我们就做一个标记，例如编号 arr[2] = 3 被选中了，那么我们可以做一个标记，例如让 arr[2] = -1，来表示 arr[2] 存放的编号已经出局的了。

然后就按照这种方法，不停着遍历数组，不停着做标记，直到数组中只有一个元素是非 -1 的，这样，剩下的那个元素就是我们要找的元素了。我演示一下吧：

这种方法简单吗？思路简单，但是编码却没那么简单，临界条件特别多，每次遍历到数组最后一个元素的时候，还得重新设置下标为 0，并且遍历的时候还得判断该元素时候是否是 -1。用这种数组的方式做，千万不要觉得很简单，编码这个过程还是挺考验人的。

这种做法的时间复杂度是 O(n * m), 空间复杂度是 O(n);

下面给出数组方法的参考代码：