约瑟夫环--通俗易懂的巧解

0x01.问题

N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。求幸存者的编号。

0x02.详细分析

约瑟夫环最容易想到的就是模拟，可以普通的用数组模拟，也可以用循环链表，用数组模拟的代码如下：

int lastRemaining(int n, int m) {
    vector<int> base(n, 1);
    m=m%n;
    int cou = 0, k = 0, i;
    for (i = 0; i < n; i++) {
        if (base[i] == 1) {
            cou++;
        }
        if (cou == m) {
            cou = 0;
            base[i] = 0;
            k++;
        }
        if (k == n - 1) {
            while (!base[i]) {
                i=(i == n - 1)? 0:i+1;
            }
            break;
        }
        if (i == n - 1) {
            i = -1;
        }
    }
    return i;
}

思路很简单，就是简单的模拟这个过程，但我们可以发现一个问题，加入n和m非常接近，但保持m<n，会发生什么情况呢？没遍历一次只能删除一个元素，并且到后期要遍历多次才能删除一个元素，假设遍历一次删除一个元素，时间复杂度已经高达O（N^N），这个时间是非常恐怖的。

当然，循环链表也可以解决这个问题，但同样的，时间复杂度也非常的高，当数据达到8位数，甚至更高时，是无法在短时间内计算出来的。所以我们需要思考其他办法。

我们重新看一下这个问题：

• 每次数到m就淘汰一人，求的是最终剩下的人。

初始时，这个序列的人数应该是n，淘汰一人后，序列的长度应该是n-1，如果我们知道长度为n-1的序列最终剩下的人数编号，是不是就可以推导出，长度为n的序列的最后一个人数编号，我们看一下如何推导：

• 长度为n的序列第一次删除的元素编号应该是m%n-1。
• 那么，如果我们把这个元素删除了，n-1的序列的开头应该就是m%n，这里假设是一个环状，处理环状问题，我们只需要取余就可以了。
• 这个相当于长度为n-1的序列每个元素都向前移动了m%n。
• 那么，如果计算得出了长度为n-1的的最后一个元素编号为x。
• 长度为n的序列的最后一个元素就应该是(m%n+x)%n
• 原因：相当于将长度为n-1序列的的最后一个元素在n的序列上再偏移m%n。

有了这个求解的思路，那么我们要求长度为n-1的最后一个元素编号，又只要求长度为n-2的最后一个元素编号，依次类推，知道长度为1，那么元素编号就是0，这就是一个递归的过程，所以我们可以用递归来解决这个问题。

有了递归的思路后，其实我们还可以使用迭代的方法来解决，递归是从n一直到1，那么迭代就可以从1到n，当然，我们也可以从2开始，迭代的表达式就是：ans=(ans+m)%i，就是递归的逆过程。

0x03.解决代码–递归

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

0x04.解决代码–迭代

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

ATFWUS --Writing By 2020–03–30