题解 | #孩子们的游戏(圆圈中最后剩下的数)#

描述
这是一道典型的约瑟夫环问题，我们可以这样理解：有n个人围成一圈，从第一个人开始报数，第m个将被杀掉，最后剩下一个，其余人都被杀掉，返回最后剩下的这个人的索引，如果没有人，则返回-1
示例

输入：
5,3
返回值：
3

方法一：环形链表
我们可以用环形链表来存储数字，每次找到被选中的元素将其移除， 删除元素的时间复杂度为，但是查找元素的时间复杂度贼为，相比于，时间复杂度会降低

• 创建环形链表存储元素

• 因为链表是环形的，所以被删除元素的索引应该对n取模，每次定位到被删除元素处直接进行remove操作，同时n需要减1

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<=0)return -1;
        List<Integer>list=new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int index=0;
        while(n>1){
            index=(index+m-1)%n;
            list.remove(index);
            n--;
        }
      return list.get(0);
    }
}

复杂度：

• 时间复杂度：由于数组移除元素的时间复杂度为循环次，所以时间复杂度为
• 空间复杂度：需要额外的辅助空间

方法二：迭代
我们知道第一个人（编号一定是) 出列之后，剩下的个人组成了一个新的约瑟夫环（以编号为= 的人开始）：
并且从开始报0。
我们把他们的编号做一下转换：

...
...

变换后就成为个人报数的子问题，假如我们知道这个子问题的解：例如是最终的胜利者，那么根据上面这个表把这个变回去刚好就是个人情况的解。可以推出来：
如何知道个人报数的问题的解,只要知道个人的解就行了,个人的解呢,就是先求的情况 ---- 这显然就是一个倒推问题。思路出来了，下面写递推公式：
令表示个人玩游戏报退出最后胜利者的编号，最后的结果是
递推公式

有了这个公式，我们要做的就是从顺序算出的数值，最后结果是。这里我们从1开始，输出
由于是逐级递推，不需要保存每个
代码如下

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<=0)return -1;
        int index=0;
        for(int j=2;j<=n;j++){
            index=(index+m)%j;
        }
        return index;
    }
}

复杂度
• 时间复杂度：只有一个循环，

• 空间复杂度：没有利用额外的辅助空间，
方法三：递归

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n==0)return 0;
        else{
           return (LastRemaining_Solution(n-1,m)+m)%n;}
    }
};

复杂度：
• 时间复杂度：递归算法的时间复杂度=递归次数*每次递归的操作次数，递归次数为,每次操作的时间复杂度为常数级,所以时间复杂度为

• 空间复杂度：递归运行时栈的大小不超过