【剑指Offer】圆圈中最后剩下的数（约瑟夫环）

短命女 2022-03-15 05:16 156阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_f78a359491e64a50bce2d89cff857eb6_tpId_13_tqId_11199_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

class Solution { 
    public:
        int LastRemaining_Solution(int n, int m)
        { 
            if(n<=1) return n-1;
            //约瑟夫环问题
            //方法1：模拟
            /*vector<bool> flag(n,false);//标记数组 int i=0;//报的数 int pos=0;//报数的小朋友的位置 int out=0;//出圈的人数 while(out!=n-1){ if(i==m-1){ flag[pos]=true; out++; i=0; pos++;pos%=n;//小朋友移动 while(flag[pos]) {pos++;pos%=n;}//去掉出圈的人 continue; } i++; pos++;pos%=n;//小朋友移动 while(flag[pos]) {pos++;pos%=n;}//去掉出圈的人 } int res=0; for(int i=0;i<n;i++) if(!flag[i]){ res=i;break; } return res;*/
            //方法2：用公式，假设f(n,m)表示最终的结果，则f(n,m)=(f(n-1,m)+m)%n,其中f(1,m)=0;
            int last=0;
            for(int i=2;i<=n;i++) last=(last+m)%i;
            return last;
            
        }
    };

[https_www.nowcoder.com_practice_f78a359491e64a50bce2d89cff857eb6_tpId_13_tqId_11199_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking