题解 | #孩子们的游戏(圆圈中最后剩下的数)#
题目： 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)，递归栈最大深度
安克创新 Anker公司福利 875人发布
查看8道真题和解析