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

题意分析

• 给出一个0-n-1的数字排列，我们最开始从0开始(包括0）走m个数字，然后将这个数字删除，然后继续执行这项操作，直到最后只剩下一个数字，问这个数字是什么？这里要注意删除了的数字就没有了，不能重复计数。
• 样例解释如下图

思路分析

解法一 指针法

• 我们可以发现，如果直接暴力进行求解的话，我们可能会遍历很多删除过的数字，这样的话时间复杂度就会很大。所以我们为了防止遍历删除过的数字，我们可以不断更新每个数字的左右两边的数字，然后我们只要走没有被删除的数字即可。所以，我们记录一下删除了多少数字，每删除一个数字，我们需要走m步。
• 代码如下
  • 我们需要删除n-1个数字，然后每次删除一个数字，我们的指针需要移动m次，所以总的时间复杂度就是O(nm)
  • 过程中我们需要开两个数组记录每个位置左右两边的数字，空间复杂度为O(n)

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n==1){
            return 0;
        }
        // 先构造每个位置的初始的左右指针的情况
        vector<int> l(n),r(n);
        for(int i=0;i<n-1;i++){
            r[i]=i+1;
        }
        r[n-1]=0;
        for(int i=1;i<=n-1;i++){
            l[i]=i-1;
        }
        l[0]=n-1;
        
        int num=0;
        int now=0; // 作为一个起始的点
        while(num<n){
            // 寻找到下一个起始的点
            for(int i=0;i<m;i++){
                now=r[now];
            }
            // 将now左边的节点删除
            int left=l[l[now]];
            l[now]=left,r[left]=now;
            num++;
        }
        
        return now;
    }
};

解法二 递归法

• 通过在网络上查找资料，我发现这其实就是一个约瑟夫问题，我们用dp(n,m)表示n个人，每次遍历到第m个人删除，最后剩下的人的编号。那么我们最初始的编号是0-(n-1)，如果我们在这个过程中删除一个编号假设为m-1，那么在下一次重新进行编号的时候，m,(m+1),(m+2)...(n-1)...就变成了0,1,2...,所以(现在的编号+m)%n=之前的编号。这样的话我们的递归方程就能使用了。

• 代码如下
  • 递归的边界是0,所以总的时间复杂度为$O(n)O(n)$
  • 每次递归需要开辟一个栈空间，总的空间复杂度为$O(n)O(n)$

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