面试题45：圆圈中最后剩下的数字

题目

$0, 1, 2, \cdots, n-1$ 这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

最简单无脑的做法是直接用链表模拟这一过程。但这样就无法发现其中的规律了。

其中有一个映射规律：

$m \rightarrow 0 \\ m+1 \rightarrow 1 \\ \vdots \\ n-1 \rightarrow n-1-m \\ 0 \rightarrow n-m \\ 1 \rightarrow n-m+1 \\ \vdots \\ m-2 \rightarrow n-2 \\$

如果左边的是自变量x，右边的函数y，那么映射规则就是：y = (x-m)%n（若x-m是负数，就加一个n再模n）。反过来，映射规则从右到左就是：y = (x+m)%n（这个就不用担心出现负数）

经过这个映射问题规模减小了1，递归解决一下就好了。

递归解法

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1 || m<1){
            return -1;
        }
        int[] array = new int[n];
        for(int i=0;i<n;i++){
            array[i]=i;
        }
        return LastRemaining_Solution(array, n, m);
    }

    private int LastRemaining_Solution(int[] array, int n, int m){
        if(n==1){
            return array[0];
        }
        int[] temp = new int[n-1];
        for(int i=0;i<n-1;i++){
            temp[i] = array[(i+m)%n];
        }
        return LastRemaining_Solution(temp, n-1, m);
    }
}

迭代解法

可以看到递归解法需要记录不必要的中间状态，因为你不知道到最后，array[0]中存放的是什么（也就是说原数组中的哪个数最后会落到array[0]里）。如果用迭代就能避免了，迭代可以直接反推出前面的数。

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