题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。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

    图片说明

  1. 解题思路

    递归 时间复杂度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;
    }