约瑟夫环问题是一个非常经典的问题。据估计，每个人都听说过它。然后我在书面测试中遇到了它。下面我将使用三种方法详细解释这个问题。在最后一种方法之后，我会保证。让你强迫它。
问题描述：编号为1-N的N名士兵坐在一起形成一个圆圈，从编号为1的士兵开始（1,2,3 .轮流报告），编号为m的士兵将在死亡后被杀死，士兵们将从1再次开始计数。直到最后一名士兵离开，询问这名士兵的号码。
1，方法一：数组
当我在大学一年级第一次遇到这个问题时，我用阵列做了这个问题。我想大多数人都知道怎么做。方法是这样的：
使用数组来存储n个数字1,2,3 . n，如图所示（这里我们假设n=6，m=3）
然后继续遍历数组，对于选定的数字，我们做一个标记，例如，选择数字arr [2]=3，然后我们可以做一个标记，例如，让arr [2]=-1，到指示存储在arr [2]中的数字已被删除。
然后按照这个方法，继续遍历数组，并继续标记，直到数组中只有一个元素为非-1，这样剩下的元素就是我们要查找的元素。让我来证明一下：
这种方法简单吗？这个想法很简单，但编码并不那么简单。有许多关键条件。每次遍历到数组的最后一个元素时，必须将下标重置为0，并且必须在遍历时判断该元素是否为-1。对手写代码感兴趣，使用这种方法做的方法，感觉不是很简单，编码过程还是相当考验的。
该方法的时间复杂度为O（n * m），空间复杂度为O（n）;
2.方法2：循环链接表
那些已经学习链表的人估计使用链表来处理约瑟夫环问题。使用链表来处理实际的想法与上面类似，但在处理链表时，所选的数字不再被标记，而是直接删除，因为从链表中删除元素的时间复杂度非常低，O（1）。当然，也可以去除上述阵列方法，但是阵列去除的时间复杂度是O（n）。所以链表的解决方案如下：
1.创建一个循环链表来存储元素：
2，然后遍历列表一次并删除它，直到列表中只剩下一个节点，我不会在这里全部演示
代码如下：
//定义链表节点
类节点{
国际日期;
节点接下来;
公共节点（int date）{
This.date=date;
}
}
核心代码
Public static int solve（int n，int m）{
如果（m==1 || n <2）
返回n;
//创建一个循环列表
节点头=createLinkedList（n）;
//遍历删除
Int count=1;
节点cur=head;
节点pre=null; //前任节点
而（head.next！=head）{
//删除节点
如果（count==m）{
Count=1;
Pre.next=cur.next;
Cur=pre.next;
}否则{
计数++;
Pre=cur;
Cur=cur.next;
}
}
返回head.date;
}
静态节点createLinkedList（int n）{
节点头=新节点（1）;
节点next=head;
For（int i=2; i＆lt;=n; i ++）{
节点tmp=新节点（i）;
Next.next=tmp;
下一个=next.next;
}
//头部和尾部连接
Next.next=head;
回头;
}
估计该方法是最有用的，时间复杂度为O（n * m），空间复杂度为O（n）。
有没有更好的办法？是的，请向下看
方法3：递归
实际上，这个问题也可以通过递归来解决。我们的想法是，每当我们删除一名士兵时，我们会对这些士兵重新编号，然后我们的难点是找到士兵在删除之前和之后的映射关系。
我们为递归函数f（n，m）定义的返回结果是幸存士兵的数量，显然当n=1时，f（n，m）=1.如果我们能找到f（n，m）之间的关系）和f（n-1，m），我们可以以递归的方式解决它。我们假设人数是n，而那些向m报告的人自杀。第一个数字是
.
1
.
m - 2
m - 1
米
m + 1
m + 2
.
.
删除后，删除编号为m的节点。删除后，只剩下n - 1个节点，删除前后的数字转换关系为：
删除之前---删除后
. --- .
m - 2 --- n - 2
m - 1 --- n - 1
m ----不（因为号码被删除了）
m + 1 --- 1（因为我下次会从这里报告）
m + 2 ---- 2
. ---- .
新环中只有n - 1个节点。删除前编号为m + 1，m + 2，m + 3的节点是删除后编号为1,2,3的节点。
假设old是删除前的节点号，new是删除节点后的号码。新旧之间的关系是旧的=（new + m - 1）％n + 1。
注意：有些人可能想知道为什么它不老=（new + m）％n？主要是因为编号从1开始，而不是从0.如果new + m==n，则最后一次计算的结果是old=0.所以old=（new + m - 1）％n + 1。
因此，我们得到f（n，m）和f（n - 1，m）和f（1，m）=1之间的关系。所以我们可以递归地做到这一点。代码如下：
Int f（int n，int m）{
如果（n==1）返回n;
返回（f（n - 1，m）+ m - 1）％n + 1;
}
我去，两行代码得到，时间复杂度是O（n），空间复杂度是O（n），牛逼！那么如果你想告诉别人，我想要一行代码来解决约瑟夫问题？答案没问题，如下：
Int f（int n，int m）{
返回n==1？ n:（f（n - 1，m）+ m - 1）％n + 1;
}
面对低谷，面试官会让你手写约瑟夫的问题，你会把这行代码扔给它。
总结
但是，当书面测试不是通过递归方法完成时，它是通过链表完成的。当时，我不知道我仍然可以使用一行代码来获取它，并且，欢迎您提供半行代码。代码得到它的方式！