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

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

输入：
5,3
返回值：
3

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

创建环形链表存储元素

图片说明

因为链表是环形的，所以被删除元素的索引应该对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);
    }
}

复杂度：

时间复杂度：由于数组移除元素的时间复杂度为 $O(m)$ 循环 $n-1$ 次，所以时间复杂度为 $O(mn)$
空间复杂度：需要额外的辅助空间 $O(n)$

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

$k --> 0$
$k+1 --> 1$
$k+2 --> 2$
...
...

$k-2 --> n-2$
变换后就成为 $（n-1）$ 个人报数的子问题，假如我们知道这个子问题的解：例如 $x$ 是最终的胜利者，那么根据上面这个表把这个 $x$ 变回去刚好就是 $n$ 个人情况的解。可以推出来： $x'=(x+k) %n$
如何知道 $（n-1）$ 个人报数的问题的解,只要知道 $（n-2）$ 个人的解就行了, $（n-2）$ 个人的解呢,就是先求 $（n-3）$ 的情况 ---- 这显然就是一个倒推问题。思路出来了，下面写递推公式：
令 $f$ 表示 $i$ 个人玩游戏报 $m$ 退出最后胜利者的编号，最后的结果是 $f[n]$
递推公式

$f[1]=0;$
$f[i]=(f[i-1]+m) mod$ $i$ $(i>1）$
有了这个公式，我们要做的就是从 $1-n$ 顺序算出 $f$ 的数值，最后结果是 $f[n]$ 。这里我们从1开始，输出 $f[n]+1$
由于是逐级递推，不需要保存每个 $f$
代码如下

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;
    }
}

复杂度
• 时间复杂度：只有一个循环， $O(n)$

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

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

复杂度：
• 时间复杂度：递归算法的时间复杂度=递归次数*每次递归的操作次数，递归次数为 $n-1$ ,每次操作的时间复杂度为常数级 $O(1)$ ,所以时间复杂度为 $O(n)$

• 空间复杂度：递归运行时栈的大小不超过 $n，O(n)$