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

题意整理

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

方法一（链表模拟）

1.解题思路

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

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // 将所有编号加入到list
        List<Integer> list=new ArrayList<>();
        for(int i=1;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.解题思路

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

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

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // 返回最后剩下的编号
        return fun(n,m)+1;
    }

    //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，所以空间复杂度为。

方法三（迭代）

1.解题思路

按照方法二递归的思路，从后往前倒推即可。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // 最后剩下编号每次所在的索引
        int index=0;

        // i表示环中元素个数
        for(int i=2;i<=n;i++){
            index=(index+m)%i;
        }
        return index+1;
    }

}

3.复杂度分析

• 时间复杂度：需要删除n-1个元素，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为。