太透彻了：约瑟夫环的三种解法
CSDN
2021-04-19 19:24
0
打开网易新闻 查看精彩图片
【CSDN 编者按】极大概率出现在面试中的约瑟夫环问题来啦java用链表实现约瑟夫环算法，本文三种方法描述解题思路，这样讲解绝对让面试官眼前一亮。
作者 | 责编 | 欧阳姝黎
前言
约瑟夫环问题是算法中相当经典的一个问题，其问题理解是相当容易的，并且问题描述有非常多的版本，并且约瑟夫环问题还有很多变形，这篇约瑟夫问题的讲解，一定可以带你理解通通！
什么是约瑟夫环问题？
约瑟夫环问题在不同平台被"优化"描述的不一样，例如在牛客剑指 offer 叫孩子们的游戏，还有叫杀人游戏，点名……最直接的感觉还是力扣上剑指 的描述：圆圈中最后剩下的数字。
问题描述：
0,1,···,n-1 这 n 个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字0开始每次删除第 3 个数字，则删除的前 4 个数字依次是2、0、4、1，因此最后剩下的数字是3。
当然java用链表实现约瑟夫环算法 太透彻了：约瑟夫环的三种解法，这里考虑 m，n 都是正常的数据范围java用链表实现约瑟夫环算法，其中
对于这个问题，你可能脑海中有了印象，想着小时候村里一群孩子坐在一起，从某个开始报数然后数到几出列，下一个重新开始一直到最后一个。不同人用不同方法解决，青铜直接模拟，钻石会优化一下，王者用公式，下面详细给大家讲解思路。
循环链表模拟
这个问题最本质其实就是循环链表的问题，围成一个圈之后，就没有结尾这就是一个典型的循环链表嘛！一个一个顺序报数，那不就是链表的遍历枚举嘛！数到对应数字的出列，这不就是循环链表的删除嘛！
打开网易新闻 查看精彩图片
链表模拟
并且这里还有非常方便的地方：
当然也有一些需要注意的地方
这样，思路明确，直接开撸代码：
class {
class node//链表节点
int val;
node(int value) {
this.val=value;
node next;
int (int n, int m) {
if(m==1) n-1;//一次一个直接返回最后一个即可
node head=new node(0);
node team=head;//创建一个链表
for(int i=1;i {
team.next=new node(i);
team=team.next;
team.next=head;//使形成环
int index=0;//从0开始计数
while (head.next!=head) {//当剩余节点不止一个的时候
//如果index=m-2 那就说明下个节点(m-1)该删除了
if(index==m-2)
head.next=head.next.next;
index=0;
else {
index++;
head=head.next;
head.val;
当然，这种算法太复杂了，大部分的 OJ 你提交上去是无法 AC的，因为超时太严重了，具体的我们可以下面分析。
有序集合模拟
上面使用链表直接模拟游戏过程会造成非常严重非常严重的超时，n 个数字，数到第 m 个出列。因为m如果非常大远远大于 n，那么将进行很多次转圈圈。
打开网易新闻 查看精彩图片
所以我们可以利用求余的方法判断等价最低的枚举次数，然后将其删除即可，在这里你可以继续使用自建链表去模拟，上面的 while 循环以及上面只需添加一个记录长度的每次求余算圈数即可：
int len=n;
while (head.next!=head) {
if(index==(m-2)%len)
head.next=head.next.next;
index=0;
len--;
else {
index++;
head=head.next;
但我们很多时候不会手动去写一个链表模拟，我们会借助 和 去模拟，如果使用 其底层也是链表，使用 的话其底层数据结构是数组。不过在使用 List 其代码方法一致。
List 可以直接知道长度，也可删除元素，使用 List 的难点是一个顺序表怎么模拟成循环链表？
咱们仔细思考：假设当前长度为 n，数到第 m 个(通过上面分析可以求余让这个有效的 m%n 不大于 n)删除，在 index 位置删除。那么删除后剩下的就是 n-1长度，index 位置就是表示第一个计数的位置，我们可以通过求余得知走下一个删除需要多少步，那么下个位置怎么确定呢？
打开网易新闻 查看精彩图片
删除3号下标
你可以分类讨论看看走的次数是否越界，但这里有更巧妙的方法，可以直接求的下一次具体的位置，公式就是为：
index=(index+m-1)%(list.size());
因为 index 是从 1 计数，如果是循环的再往前 m-1 个就是真正的位置，但是这里可以先假设先将这个有序集合的长度扩大若干倍，然后从 index 计数开始找到假设不循环的位置 ，最后我们将这个位置 %(集合长度)即为真正的长度。
打开网易新闻 查看精彩图片
真实位置计算
使用这个公式一举几得，既能把上面m过大循环过多的情况解决，又能找到真实的位置，就是将这个环先假设成线性的然后再去找到真的位置，如果不理解的话可以再看看这个图：
打开网易新闻 查看精彩图片
这种情况的话大部分的 OJ 是可以勉强过关的，面试官的层面也大概率差不多的，具体代码为：
class {
int (int n, int m) {
if(m==1)
n-1;
=new ();
for(int i=0;i {
list.add(i);
int index=0;
while (list.size()>1)
index=(index+m-1)%(list.size());
list.(index);
list.get(0);
递归公式解决
我们回顾上面的优化过程，上面用求余可以解决 m 比 n 大很多很多的情况(即理论上需要转很多很多圈的情况)。但是还可能存在 n 本身就很大的情况，无论是顺序表 还是链表 去频繁查询、删除都是很低效的。
所以聪明的人就开始从数据找一些规律或者关系。
先抛出公式：
f(n,m)=(f(n-1,m)+m)%n
f(n,m)指n个人，报第m个编号出列最终编号
下面要认真看一下我的分析过程：
我们举个例子，有0 1 2 3 4 5 6 7 8 9 十个数字，假设 m 为 3,最后结果可以先记成f(10,3)，即使我们不知道它是多少。
当进行第一次时候，找到元素 2 删除，此时还剩 9 个元素，但起始位置已经变成元素 3。等价成3 4 5 6 7 8 9 0 1这 9 个数字重写开始找。
打开网易新闻 查看精彩图片
f(10,3)删除第一个数
此时这个序列最终剩下的一个值即为f(10,3)，这个序列的值和 f(9,3)不同，但是都是 9 个数且 m 等于 3，所以其删除位置是相同的，即算法大体流程是一致的，只是各位置上的数字不一样。所以我们需要做的事情是找找这个序列上和f(9,3)值上有没有什么联系。
寻找过程中别忘记两点，首先可通过%符号对数字有效扩充，即我们可以将 3 4 5 6 7 8 9 0 1这个序列看成(3,4,5,6,7,8,9,10,11).这里的10即为此时的n数值。
另外数值如果是连续的，那么最终一个结果的话是可以找到联系的(差值为一个定制)。所以我们可以就找到f(10,3)和f(9,3)值之间结果的关系，可以看下图：
打开网易新闻 查看精彩图片
f(10,3)删除一次和f(9,3)
所以f(10,3)的结果就可以转化为f(9,3)的表达,后面也是同理：
f(10,3)=(f(9,3)+3)
f(9,3)=(f(8,3)+3)%9
f(2,3)=(f(1,3)+3)%2
f(1,3)=0
这样，我们就不用模拟操作，可以直接从数值的关系找到递推的关系，可以轻轻松松的写下代码：
class {
int index=0;
int (int n, int m) {
if(n==1)
0;
((n-1,m)+m)%n;
但是递归效率因为有个来回的规程，效率相比直接迭代差一些，也可从前往后迭代：
class {
int (int n, int m) {
int value=0;
for(int i=1;i
文章来源:https://3g.163.com/dy/article_cambrian/G7VICE6A0511FQO9.html?id=117566028830.pdf