[劍指Offer]面試題62：圓圈中最後剩下的數字（約瑟夫環問題）

0,1,n-1這n個數字排成一個圓圈，從數字0開始，每次從這個圓圈裡删除第m個數字。求出這個圓圈裡剩下的最後一個數字。

例如，0、1、2、3、4這5個數字組成一個圓圈，從數字0開始每次删除第3個數字，則删除的前4個數字依次是2、0、4、1，是以最後剩下的數字是3。

示例 1：

輸入: n = 5, m = 3

輸出: 3

示例 2：

輸入: n = 10, m = 17

輸出: 2

限制：

1 <= n <= 10^5

1 <= m <= 10^6

思路：

這道題目一般分為兩種解法：模拟法和數學法。

模拟法顧名思義，按照題目給出的要求模拟一個循環連結清單，依次找出第m個數字，直至剩一個數字為止。

數學法相對難了解一點，需要分析每次被删除數字的規律，然後計算出最後剩下的數字。

• 從n個數字取出第m個數字，記為f(n,m)
• 在n個數字中，記第一個被删除的數字k=(m-1)%n，這裡之是以要對n取模，是要考慮到m>n的輸入。
• 取出一個數字後，剩下的數字組成了一個新的循環連結清單，k+1成為了連結清單的起點，舊連結清單與新連結清單的映射如下：

k+1	→
k+2	→	1
…	…	…
n-1	→	n-k-2
→	n-k-1
1	→	n-k
…	…	…
k-1	→	n-2
…	…	…

• 映射p(x)=(x-k-1)%n，此時k+1為第一個數字，即前k-1個數字接到了隊尾，是以新連結清單的序号都減去k-1，然後對n取模，保證序号不超過n-1，需要注意的是這裡涉及到了負數取模，而不同語言對負數取模的結果是不一樣的（負數取模）。
• p的逆映射 p − 1 p^{-1} p−1(x)=(x+k+1)%n，也可以直接根據上面的映射推導出此式。

• 此時，對n-1個數字取出第n個數字，記為f’(n-1,m)，根據映射關系可以進行如下推導：

  f ′ ( n − 1 , m ) = p − 1 [ f ( n − 1 , m ) ] = [ f ( n − 1 , m ) + k + 1 ] f'(n-1,m)=p^{-1}[f(n-1,m)]=[f(n-1,m)+k+1]%n f′(n−1,m)=p−1[f(n−1,m)]=[f(n−1,m)+k+1]

  代入k=(m-1)%n

  f ( n , m ) = f ′ ( n − 1 , m ) = [ f ( n − 1 , m ) + m ] f(n,m)=f'(n-1,m)=[f(n-1,m)+m]%n f(n,m)=f′(n−1,m)=[f(n−1,m)+m]

  根據上式，可以用遞歸或循環計算粗最後剩下的數字。

代碼：

# LeetCode, Python3
class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        if n == 1:
            return 0
        last = 0
        for i in range(2,n+1):
            last = (last + m) % i
        return last