關注公眾號 長歌大腿，發(fā)送“機器學習”關鍵字，可獲取包含機器學習（包含深度學習)，統(tǒng)計概率，優(yōu)化算法等系列文本與視頻經(jīng)典資料，如《ESL》《PRML》《MLAPP》等。

題目描述：

0,1,,n-1這n個數(shù)字排成一個圓圈，從數(shù)字0開始，每次從這個圓圈里刪除第m個數(shù)字。求出這個圓圈里剩下的最后一個數(shù)字。

例如，0、1、2、3、4這5個數(shù)字組成一個圓圈，從數(shù)字0開始每次刪除第3個數(shù)字，則刪除的前4個數(shù)字依次是2、0、4、1，因此最后剩下的數(shù)字是3。

示例 1：

輸入: n = 5, m = 3
輸出: 3
示例 2：

輸入: n = 10, m = 17
輸出: 2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

解題思路：

根據(jù)題目描述，這是一個典型的約瑟夫環(huán)問題，如果用模擬方法來求解，則復雜度為的時間復雜度。在m,n很大時不可接受。
我們觀察得到，當還有J個數(shù)字時，刪除該時候的第m個數(shù)字，剩下的數(shù)字在進行下一次報數(shù)過程中下角標從刪除數(shù)字的位置開始，老序列下角標為的話則新序列的下角標為（在同余類的表示情況），其中p為上次的下角標。故，反過來，假設已知新序列的下角標為，則上一次序列的角標為，其遞推關系式可寫為：

代碼實現(xiàn)（Java）:

class Solution {
    public int lastRemaining(int n, int m) {
        int p=0;
        for(int i = 2; i <= n; i++){
            p = (p+m)%i;
        }
        return p;
    }
}

實現(xiàn)分析：

實現(xiàn)算法復雜度為O(n)。