题解 | #环形链表的约瑟夫问题#

题意：

• n个人成环，编号从1到n，从1开始报数，报数到m的人离开，由下一个人继续从1开始报数，循环n-1轮之后只剩下一个人，求这个人的初始编号是多少。

方法一：

思路分析：

• 因为最后只剩下一个人，所以我们可以从最后剩下的编号入手，看能不能倒推得到最开始的编号。首先画出图尝试找一下规律。
  
• 如上图所示，我们倒推：
  第四轮结束，最后留下来的人的编号为 1；
  第三轮结束，最后留下来的人的编号为 1+2=3; 3%2=1,编号为1；
  第二轮结束，最后留下来的人的编号为 1+2=3;
  第一轮结束，最后留下来的人的编号为 3+2=5(因为5>4) 所以5%4=1;
  第一轮开始，最后留下来的人的编号为 1+2=3;
• 我们可以得到规律是，(x+m-1)%n+1 是倒推的规律。此处先-1，+1的原因是初始从1开始编号，编号范围[1,n]与取模运算的值域范围[0,n-1]有差异，所以需要先减一后加一。如果编号范围是[0,n-1]的话，那么该规律应该为(x+m)%n
• 下面我们对于该规律(x+m)%n的一般化验证。
  
• 因此利用(x+m-1)%n+1的规律递推即可得到答案。

代码如下：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        int x=1;//x为留下来的人在最后一轮结束后的编号
        for(int i=2;i<=n;i++){
            x=(x+m-1)%i+1;//i为每轮人数数量。从2->n
        }
        return x;
    }
};

复杂度分析：

时间复杂度：，循环n-1轮。
空间复杂度：。

方法二：

根据上述的递推式，也可使用递归的方式来解决。使用函数f(n,m)来表示人数为n时，最后留下来的人的编号。
有(f(n-1,m)+m-1)%n+1=f(n,m)。

代码如下：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int helper(int n,int m){
        if(n==1)
            return 1;
        int x=helper(n-1,m);//下一轮的编号
        return (x+m-1)%n+1;//递推公式
    }
    int ysf(int n, int m) {
        // write code here
        return helper(n,m);
    }
};

复杂度分析：

时间复杂度：，递归次数。
空间复杂度：，递归深度。