圆圈中最后剩下的数字

Leetcode Link: 剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode）

题目

解法一

思路： 模拟解法，时间复杂度 $O(mn)$，超时

题解：

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        nums = [x for x in range(n)]
        cnt = 0
        i = 0
        while(len(nums)>1): # 开始遍历，直到数组里只剩一个为止
            cnt += 1
            if cnt == m:
                nums.pop(i)
                cnt = 0
                if i >= len(nums): i = 0
                continue # 此时i不变，因为由于 pop 导致下一个数字前推一位，但是如果溢出了需要变成0
            i += 1
            if i >= len(nums):
                i = 0
        return nums[0]

解法二

思路：这是一个经典的约瑟夫环问题

题解来源：约瑟夫环——公式法（递推公式）_陈浅墨的博客-CSDN博客_约瑟夫环公式

[! Conclusion] 先给出结论 约瑟夫环问题的递推公式为

$$f(n,m)=(f(n-1,m)+m)\%n$$

$f(n,m)$ 表示，$n$ 个人报数，每报到 $m$ 时杀掉那个人，最终胜利者的编号. $f(n-1,m)$ 表示，$n-1$ 个人报数，每报到 $m$ 时杀掉那个人，最终胜利者的编号.

[! Example]- 详细示例 下面我们不用字母表示每一个人，而用数字。 1 、 2 、 3 、 4 、 5 、 6 、 7 、 8 、 9 、 10 、 11

表示 11 个人，他们先排成一排，假设每报到 3 的人被杀掉。

• 刚开始时，头一个人编号是 1，从他开始报数，第一轮被杀掉的是编号 3 的人。
• 编号 4 的人从 1 开始重新报数，这时候我们可以认为编号 4 这个人是队伍的头。第二轮被杀掉的是编号 6 的人。
• 编号 7 的人开始重新报数，这时候我们可以认为编号 7 这个人是队伍的头。第三轮被杀掉的是编号 9 的人。
• ……
• 第九轮时，编号 2 的人开始重新报数，这时候我们可以认为编号 2 这个人是队伍的头。这轮被杀掉的是编号 8 的人。
• 下一个人还是编号为 2 的人，他从 1 开始报数，不幸的是他在这轮被杀掉了。
• 最后的胜利者是编号为 7 的人。

其过程如下所示，每次杀掉一个人后，重启一行计数

现在再来看我们递推公式是怎么得到的！ 将上面表格的每一行看成数组，这个公式描述的是：幸存者在这一轮的下标位置

根据结论即可写出题解 题解： 递归写法：直接按照结论来写

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
    
        def f(n,m):
            if n == 0: return 0
            return (f(n-1, m)+m) % n
        
        return f(n,m)

迭代写法（逆推结论）：我们知道最后一个胜利者下标一定是 0，希望通过逆推的方式找到这个胜利者最初所在的位置，参考答案

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        f = 0  # 最后剩下一个人的情况时胜利者的下标是0
        # 开始逆推
        for x in range(2, n+1):
            f = (m+f)%x # 循环右移m位
        return f

启发和联系