经典面试题：n个数字（0,1,…,n-1）形成一个圆圈

题目：

n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。

我的思路：

这是个很经典的环形问题，最优的方案时间复杂度是O(n)：先构建递推公式，再使用循环或者递归都能轻松求解，

网上的教程很少能把这个递推公式的由来描述清楚，所以我在这里加入我的一些理解。

由于我们要求解的是n个元素，第m个数字，要找到最后的一个数字，那么我在这里假设得到的结果是f(n,m),

假设我们已有数列为：

0 1 ... m-2 m-1 m ... n-1

删除一次后得到的新数列是（注意题目条件->从被删除数字的下一个继续删除）：

m m+1 ... n-1 0 1 ... m-2 ①

很显然，通过一次删除后，问题规模从n变成了n-1,而f(n-1,m)所要求解的数列是：

0 1 ... m-2 m-1 m ... n-2 ②

很显然，把数列②向左移动m就变成了①的解（注意①和②不完全相同，但是我们想要求的是第一个值，因为第一个值是删除后剩下的数字），

考虑到“左加右减”的数学原理和环形的特征，得到递推公式：

0 if n==1

f(n,m)={

(f(n-1,m)+m)%n if n>1

那么也就不难得到如下代码：

int LastNumberOfCircle(int n, int m)

{

    int last = ;

    for(int i=;i<=n;++i)

    {

        last = (last+m)%i;

    }

    return last;

}

巴特西