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

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

题意分析：

这是一个著名问题约瑟夫环问题。

示例输入：n=5,m=3
返回：3
现在有5个小孩，围成一圈，编号从0-4。编号0的孩子从0开始报数，当有小孩报到3-1=2时，该小孩出局。一直到最后剩下的3号小孩。

过程图如下：

图片说明

题解一（模拟）：

我们使用数组模拟这一过程。新建一个数组长度为n。每次数到m-1，就把该元素弹出。

我们使用tmp = (tmp+ m-1+l.size())%l.size()找出我们应该删除哪一个元素。这看上去有规律可循。我们在初始化tmp=0，根据公式，我们下一步删除的是索引为2的元素。下一次，根据公式，我们要删除的是vector中tmp=(2+2+4)%4=0，索引为0的元素。下一步删除的是tmp=(0+2+3%3)=2,要删除的是vector中索引为2的元素。下一步删除的是索引为0的元素。根据上面的过程图，可以看到最后结果为留下的数字为3.

int lastRemaining(int n, int m) {
    vector<int>l;
    for(int i=0;i<n;i++){
        l.push_back(i);
    }
    int tmp = 0;
    while(l.size()>1){
        tmp = (tmp+ m-1+l.size())%l.size();
        auto i =l.begin()+tmp;
        l.erase(l.begin()+tmp);
    }
    return *l.begin();
}

时间复杂度： $O(nm)$ 。当m和n特别大的时候，模拟法耗时，空间都巨大，不适合。

题解二（找规律）：

我们将上面公式进行反向推导，避免删除vetor中的元素。

假设 $f(N,M)$ 表示N个人报数，报到M时最后的结果。

当把第i个小孩移除，下一个人成为开始报数的人，相当于把数组向前移动了M位。
比如一开始报数的孩子是0号孩子，在报到2时，2号孩子被移出，3号孩子成为第一个报数的人。我们可以把3号孩子所在的索引认为是起始位置0。相较于孩子0的位置，就是把数组向前移动了M位。

现在看 $f(N,M)$ 和 $f(N-1,M)$ 的关系。 $f(N,M)=(f(N-1,M)+M)%N$ 。 $f(N,M)$ 在 $f(N-1,M)$ 看来，就在其后M个位置。

int LastRemaining_Solution(int n, int m) {
    if (n <= 0) {
        return -1;
    }
    int p = 0;
    for (int i = 2; i <= n; i++) {
        p = (p + m) % i;
    }
    return p;
}

时间复杂度： $O(N)$

空间复杂度： $O(1)$