面试题45：圆圈中最后剩下的数字
题目
这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
最简单无脑的做法是直接用链表模拟这一过程。但这样就无法发现其中的规律了。
其中有一个映射规律：
如果左边的是自变量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;
}
