剑指offer 62 约瑟夫问题

n个人, 每m个数就杀掉一个人

其实这是一个数学问题.

我们只关注活着的那个人(我们称之为幸运儿)的序号变化:

image.png

正这不好看我们从下往上看. 如下图, 从N = 7 反推N = 8

image.png

我们可以得到, 索引(也称为活着的人数)为N时, 幸运儿的位置, 是索引N-1时的位置 + m, (此时数组长度溢出, 因此要余索引N),得到N时幸运儿的位置.

最后一次我们知道幸运儿位置一定是0, 且这次的索引是1, 因此我们从索引2开始一直推到索引N, 也就是所有人的总数n, 取此时的位置变量, 就是最终结果.

代码很简单

int lastRemaining(int n, int m){
    int pos = 0;
    for(int i = 2; i<=n; i++)
    {
        pos = (pos + m) % i;
    }
    return pos;
}