前往此题

解题思路

这道著名的约瑟夫环问题，必须得写一篇博客记录一下啊~

本题以n = 5，m = 3 为例:

为了更形象的体现环，我们以[0, 1, 2, 3, 4, 0, 1, 2, 3, 4]来模拟这个环

直接上图：

算法过程

1. 第一轮数组为[0, 1, 2, 3, 4], 从0开始，所以删除2
2. 到了第二轮数组中剩下[0, 1, 3, 4]，由于从3开始所以是[3, 4, 0, 1, 3, 4, 0, 1],最终删除0
3. 到了第三轮数组中剩下[1, 3, 4], 由于从1开始所以是[1, 3, 4, 1, 3, 4], 最终删除4
4. 到了第四轮数组中剩下[1, 3], 由于从1开始所以是[1, 3, 1, 3], 最终删除1

此时环只剩下3，此为最终答案。

公式推导

我们抛开前面的图来做一个逻辑推导过程：

现在我们有n个数，所以这些数的范围就是0到n-1。因为每次都要数m个数，然后进行删除，最后剩下的就是最终结果。

我们可以假设一个公式: y = f(n, m) ，这个y指的是要删除的数的下标。如[0, 1, 2, 3, 4]中3的x的下标为y=3，我们从下标为0开始数1、2、3、4，第4个就是数组中的3就是我们第一轮要的结果。

现在我们已经删除一个了，这个时候公式已经变成x = f(n-1, m)。

取余的操作就不用讲了吧，题目中可能会出现m > n的情况，因为考虑到环，所以用取余的方式来得到最终结果。

问题来了：第一个删掉的数字和第二个删掉的数字之间有什么联系？

可以发现第一个被删除数与第二个删除数之间的下标差为m-1，记为(m-1)%n

得到公式：f(n, m) = ((m-1) % n + x + 1)%n, 其中x = f(n - 1, m)

所以：

• f(n, m) = [(m - 1) % n + x + 1] % n
• f(n, m) = [(m - 1) % n % n + (x + 1) % n] % n
• f(n, m) = [(m - 1) % n + (x + 1) % n] % n
• f(n, m) = (m - 1 + x + 1) % n
• f(n, m) = (m + x) % n

最后上代码

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