约瑟夫环的三种解法

算法中相当经典的一个问题，其问题理解是相当容易的，并且问题描述有非常多的版本，并且约瑟夫环问题还有很多变形，这篇约瑟夫问题的讲解，一定可以带你理解通通!

什么是约瑟夫环问题?

约瑟夫环问题在不同平台被"优化"描述的不一样，例如在牛客剑指offer叫孩子们的游戏，还有叫杀人游戏，点名……最直接的感觉还是力扣上剑指offer62的描述：圆圈中最后剩下的数字。

问题描述：

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

当然，这里考虑m，n都是正常的数据范围，其中

• 1 <= n <= 10^5
• 1 <= m <= 10^6

对于这个问题，你可能脑海中有了印象，想着小时候村里一群孩子坐在一起，从某个开始报数然后数到几出列，下一个重新开始一直到最后一个。不同人用不同方法解决，青铜直接模拟，钻石会优化一下，王者用公式，下面详细给大家讲解思路。

循环链表模拟

这个问题最本质其实就是循环链表的问题，围成一个圈之后，就没有结尾这就是一个典型的循环链表嘛!一个一个顺序报数，那不就是链表这里还有非常方便的地方：

• 循环链表的向下枚举不需要考虑头尾问题，直接node=node.next向下
• 循环链表的删除也不需要考虑头尾问题，直接node.next=node.next.next删除

当然也有一些需要注意的地方

• 形成环形链表很简单，只需要将普通链表的最后一个节点的next指向第一个节点即可
• 循环链表中只有一个节点的时候停止返回，即node.next=node的时候
• 删除，需要找到待删除的前面节点，所以我们删除计数的时候要少计一位，利用前面的那个节点直接删除后面节点即可

这样，思路明确，直接开撸代码：然，这种算法太复杂了，大部分的OJ你提交上去是无法AC的，因为超时太严重了，具体的我们可以下面分析。

有序集合模拟

上面使用链表直接模拟游戏过程会造成非常严重非常严重的超时，n个数字，数到第m个出列。因为m如果非常大远远大于m，那么将进行很多次转圈圈。

（编辑：济南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!