题解 | #孩子们的游戏(圆圈中最后剩下的数)#

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

题目分析：
首先这题要每次删除一个数，可以使用数组或者链表解决这一题，数组可以O(1)查找 O(n)删除，链表可以O(1)删除，O(n)查找，果然，鱼和熊掌不可兼得（块状链表貌似可以兼得hh）但是这题实际上是约瑟夫环问题，我看题解上没有写的很清楚的。。。
首先先给出链表的做法
算法1：链表

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n <= 0) return -1; 
            //人数为0
        list<int> lt;
            //直接用stl里面封装好的链表即可
        for (int i=0; i<n; ++i) lt.push_back(i); 放入n个人 int index="0;" 要删除的人 while (n> 1) {
            index = (index + m - 1) % n;
                //n个人，从index开始报数，报到m-1的人
            auto it = lt.begin();
            std::advance(it, index); 
            //该函数可以将it向后移动index个位置
            lt.erase(it);
            //删除链表元素
            --n;
        }
        return lt.back();
    }
};

很经典的链表的使用不在细说，下面来说一说约瑟夫环问题
实际上这题就是约瑟夫环问题

理解了上面，这就很简单了
算法2：递推

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if( n <= 0 || m <= 0 )     return -1;  
        int ans = 0 ;
        //最后一个删除的肯定是0
        for(int i =  2; i <= n ; i++){
            ans = ( ans + m ) % i;
               //这一次删除的数=（上一次删除的数+m）%（上一次剩的人数）
        }
        return ans;
    }
};

时间复杂度O(n)
空间复杂度O(1)
代码非常优美简洁，效率十分高