题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

约瑟夫问题

1. 公式结论

   f(N,M)=(f(N−1,M)+M)%N.

   f ( N , M ) f(N,M)f(N,M)表示，N个人报数，每报到M的人编号
   f ( N − 1 , M ) f(N-1,M)f(N−1,M)表示，N-1个人报数，每报到M的人编号

2. 公式推演

   假设有7个人，每次报到3的人是需要出局的人

   下图中黄色字体表示从第一轮到最后一轮，红色字体表示每一轮的第一个报数的人，绿色字体表示胜利者

   从第8轮倒退 f(1,3) 表示只剩下一个人的时候那么这个人就是胜利者，胜利者的下标为1

   f(2,3) = (f(1,3) + 3) % 3 = 1 ， 剩余两人出局的下标为1

   f(3,3) = (f(2,3) + 3) % 3 = 1, 剩余三人 出局的下标为1

   …………

   f(8,3) = (f(7,3) + 3) % 3 = 3 ， 剩余8人出局的人下标为3

   

3. 解题思路

   递归 时间复杂度O(n)，空间复杂度O(n)

   由公式可以得到当N=1时，为递归退出条件, 可以得到递归代码为

   public class Solution {
       public static int LastRemaining_Solution(int n, int m) {
           //递归结束条件
           if (n == 1) {
               return 0;
           }
           // f(n.m) = (f(n,m) + m) % n
           return (LastRemaining_Solution(n - 1, m) + m) % n;
       }
   }

   非递归 时间复杂度O(n) 空间复杂O(1)

   从公式推演中可以得知

   当我们知道1轮出局的为编号3，那么第二轮出局的是编号多少？是编号6，那么我们如果以每次开头的编号做一张图，则为下图

   所以当我们知道第一轮淘汰的下标为3，那么第二轮淘汰的下标为多少呢，由于第一轮删除了下标为3，整体数据全部向前位移三位那么，下一次被删除的下标为3，依次类推
   

       public static int LastRemaining_Solution(int n, int m) {
           if(n == 0){
               return -1;
           }
           int p=0;
           for(int i=2;i<=n;i++)
           {
               p=(p+m)%i;
           }
           return p;
       }