面試題45：圓圈中最后剩下的數(shù)字
題目
這n個數(shù)字排成一個圓圈惕它，從數(shù)字0開始每次從這個圓圈里刪除第m個數(shù)字届榄。求出這個圓圈里剩下的最后一個數(shù)字。
最簡單無腦的做法是直接用鏈表模擬這一過程刊懈。但這樣就無法發(fā)現(xiàn)其中的規(guī)律了歌溉。
其中有一個映射規(guī)律：
如果左邊的是自變量x，右邊的函數(shù)y瓶颠，那么映射規(guī)則就是：y = (x-m)%n（若x-m是負(fù)數(shù)拟赊，就加一個n再模n）。反過來粹淋，映射規(guī)則從右到左就是：y = (x+m)%n（這個就不用擔(dān)心出現(xiàn)負(fù)數(shù)）
經(jīng)過這個映射問題規(guī)模減小了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);
}
}
迭代解法
可以看到遞歸解法需要記錄不必要的中間狀態(tài)，因為你不知道到最后屋匕，array[0]中存放的是什么（也就是說原數(shù)組中的哪個數(shù)最后會落到array[0]里）葛碧。如果用迭代就能避免了，迭代可以直接反推出前面的數(shù)过吻。
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;
}
