CodingInterview-孩子们的游戏(圆圈中最后剩下的数)

这道题使用链表（或用 list 模拟链表）的方法实现起来比较简单，就不做实现了。主要讨论一下它的数学规律。

首先，这道题实际上是一个约瑟夫环问题，可以推到出迭代公式，从而用很简单的代码解决问题。

我们假设环的长度为 n，而每次删除第 m 个数字。

现在我们来看第一轮，先假设删除的数字为 k，那么删除前后的序列如下：

删除前：0  ,...,k-1,k,k+1,...,n-1
删除后：0  ,...,k-1, ,k+1,...,n-1
重编号：k+1,...,n-2, ,0  ,...,n-k-2

而且，通过题意（每次删除第 m 个数字）我们还可以知道，k=m%n-1，所以 k+1=m%n。

接着，因为第二轮是从被删除的下一个数字开始，也就是从 k+1 开始，所以我们重新编号，令k+1=>0，那么根据这个关系，就可以得到k+2=>1、n-1=>n-k-2、k-1=>n-2。

那么，假设第一轮中某一个数字的编号为 X(n),第二轮中某一个数字的编号为 X(n-1)，是不是就可以得到递推公式X(n)=(X(n-1)+k+1)%n （n>=1）。

那么，如果知道 X(1)，就可以求得所有的解了。而很显然地，在只有 1 个数字的时候，弹出的数字的序号为 0，所以X(1)=0。

现在，已经得到了解题的所有条件，可以开始编码了，代码十分简单。

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<1 || m<1) return -1;
        int x=0;
        for(int i=2;i<=n;i++){
            x=(x+m)%i;
        }
        return x;
    }
};

参考：约瑟夫环的公式推导