[剑指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