解题思路
约瑟夫问题的数学解法思路与动态规划类似。将问题答案记为,该值代表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); } }