题意整理

• 有n个小朋友围成一圈，编号分别是0到n-1。
• 每次报道第m-1个小朋友，则第m-1个小朋友出圈，求最后剩下的那个小朋友的编号。

方法一（链表模拟）

1.解题思路

一种最容易想到的方法是用链表模拟这个过程。首先将0到n-1这n个数依次加入到list链表，每次模拟题目要求，删除指定位置的元素，剩下的那一个即是最后的数字。 由于每次报数list容量就减一，所以即将出环的那个数对应的索引也要前移一位，故每次删除的索引为 $index=(index+m-1)mod(list\mathrm{.}size())index=(index+m-1)mod(list.size())$。

2.代码实现

import java.util.*;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        // 将所有编号加入到list
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(i);
        }

        int index=0;
        while(list.size()>1){
            //每次删除的索引
            index=(index+m-1)%list.size();
            list.remove(index);
        }
        return list.get(0);
    }
}

3.复杂度分析

• 时间复杂度：需要删除n-1个元素，每次删除的时间复杂度为 ，所以时间复杂度为 。
• 空间复杂度：需要额外的 的链表存储元素，所以空间复杂度为 。

方法二（递归）

1.解题思路

假设初始编号为0，1，……，n-1，它们对应的索引分别是0，1，……，n-1。

• 终止条件：当最后只剩一个元素时，我们知道这个元素的索引是0
• 递推关系：我们可以根据索引值推算出上一次这个剩余元素所在索引，……一直到有n个元素时，这个元素所在索引等于它本身的值。每一层的索引之间是有一个递推关系的，即：
• 举例说明： 比如0，1，2，3，4，当删除一个数字2后，还剩4个数字，分别是3、4、0、1，此时是n-1个元素，3所在下标为0，往前补m(m=3)个元素，分别是0、1、2、3、4、0、1，此时是n个元素的情况，下标$3=(0+3)mod(5)3=(0+3)mod(5)$ ，即 。n个元素时，下标3正好对应编号3。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        // 返回最后剩下的编号
        return fun(n,m);
    }
    
    //fun(n，m)表示环中有n个元素时，最后出环元素的索引
    private int fun(int n,int m){
        //递归终止条件
        if(n==1) return 0;
        
        //每一层的返回值
        return (fun(n-1,m)+m)%n;
    }
}

3.复杂度分析

• 时间复杂度：需要删除n-1个元素，所以时间复杂度为 。
• 空间复杂度：递归栈的深度为n，所以空间复杂度为。