题解 | #孩子们的游戏(圆圈中最后剩下的数)#

题目： https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6 约瑟夫问题

法一：用队列模拟。 列表右边做队头，列表左边做队尾。 但是n和m过大的时候，执行时间超时。

class Solution:
    def LastRemaining_Solution(self , n: int, m: int) -> int:
        simqueue=list(range(n-1,-1,-1))
        while len(simqueue)>1:
            for i in range(m-1):
                simqueue.insert(0,simqueue.pop())
            simqueue.pop()
        return simqueue.pop()

时间复杂度：O(mn)

空间复杂度：O(n)

法二：用公式递归

旧编号： 0 1 2 3 ... m-1 m m+1 ... n-1

去除第m-1个元素后

新编号：-m 1-m 2-m 3-m ... x 0 1 ... n-1-m

递推关系 f(n,m)=(f(n-1,m)+m) % n

(看了一些题解，对这个递推关系的得来也是朦朦胧胧地理解...)

import sys
sys.setrecursionlimit(100000)
class Solution:
    def LastRemaining_Solution(self , n: int, m: int) -> int:
        if n==1:
            return 0
        else:
            return (self.LastRemaining_Solution(n-1,m)+m)%n

时间复杂度：O(n)，每个元素访问一次

空间复杂度：O(n)，递归栈最大深度