面试问到约瑟夫环问题，三种方法拿捏了！

约瑟夫环问题

前言

大家好，我是bigsai！

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

什么是约瑟夫环问题？

约瑟夫环问题在不同平台被"优化"描述的不一样，例如在牛客剑指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的时候

• 删除，需要找到待删除的前面节点，所以我们删除计数的时候要少即一位，利用前面的那个节点直接删除后面节点即可

这样，思路明确，直接开撸代码：

class Solution {
    class node//链表节点
    {
        int val;
        public node(int value) {
            this.val=value;
        }
        node next;
    }
    public int lastRemaining(int n, int m) {
        if(m==1)return n-1;//一次一个直接返回最后一个即可
        node head=new node(0);
        node team=head;//创建一个链表
        for(int i=1;i<n;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;
        }
        return head.val;
    }
}

当然，这种算法太复杂了，大部分的OJ你提交上去是无法AC的，因为超时太严重了，具体的我们可以下面分析。

有序集合模拟

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

所以我们可以利用的方法判断等价最低的枚举次数，然