解题思路
约瑟夫问题的数学解法思路与动态规划类似。将问题答案记为,该值代表n个人报数为m时留下来的编号。现在需要确定与的关系。
对于第一次删除,长度为n的序列的第m%n个元素会被选中。删除之后序列长度为n-1。假设我们已经知道与的值,假设,,经过下图的排列方法之后,应该指向同一个元素。
如:
数组元素:{1,2,3,4,5} 开始一共5个人 n=5 每次报数到2的时候 离开 即m=2
数组index:{0,1,2,3,4}
第一次:从1开始报数 即从数组下标为0的1开始,报数到2的时候数组下标为1的2离开,{1,3,4,5}
第二次:因为2离开后,从3开始报数了,此时数组应该顺序应该是{3,4,5,1} 对应数组下标:{0,1,2,3},此时元素3变为了数组下标为0的元素,
然后报数,到数组下标仍然为1的4元素离开,所以此时可以发现规律:
即:从头开始数图片说明 位置的元素等于从第一次删除位置数图片说明 位置的元素(即:2次被删除的元素都是数组下标为1的)。根据此等式关系,结合第一次删除位置为m%n的条件,我们可以得到二者的递推关系。
图片说明
根据上述递推关系可以得到递推写法。
反推过程:(当前index + m) % 上一轮剩余数字的个数
最终剩下一个人时的安全位置肯定为1,反推安全位置在人数为n时的编号
人数为1: 0+1
人数为2: (0+m) % 2+1
人数为3: ((0+m) % 2 + m) % 3+1
人数为4: (((0+m) % 2 + m) % 3 + m) % 4+1
该方法直接采用数学公式法进行推导,所以时间复杂度为图片说明 ,没有用到额外的内存空间,空间复杂度为图片说明

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {

        // 计数从1开始
        return f(n, m) + 1;
    }

    public int f (int n, int m) {

       // 边界情况
        if (n == 1) {
            return 0;
        }
        // 递归关系
        return (m + f(n - 1, m)) % n;
    }
}

解法2:

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {

        if(n==1 && m==1){
            return -1;
        }

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