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

如果要求空间复杂度为O(1)，我们就不能使用辅助空间来模拟过程了，需要找到每次报数的规律。

思路：设f(n,m)为0~n-1的圆圈中每次报数m-1时最后剩下的数字，我们尝试找出f(n,m)和f(n-1,m)的关系规律。

class Solution {
public:  // f(n,m) = (f(n-1,m) + m) % n   
    int LastRemaining_Solution(int n, int m) {
        if (m < 1) {
            return -1;
        }
        
        int fpre = 0;
        int fcur = 0;
        for (int i = 1; i < n; i++) {
            fcur = (fpre + m) % (i + 1);
            fpre = fcur;
        }
        
        return fcur;
    }
};