约瑟夫环

方法一约瑟夫环 递归

正经的约瑟夫换问题，证明过程约瑟夫环

参考代码

  1. class Solution:
  2.     def findTheWinner(self, n: int, k: int) -> int:
  3.         return self.ring(n,k) + 1
  4.     def ring(self, n,k):
  5.         if n == 1:
  6.             return 0
  7.         return (self.ring(n-1,k) + k ) % n

复杂度分析

时间复杂度 O(n)
空间复杂度 O(n) 递归栈空间开销

方法二约瑟夫环迭代

  1. class Solution:
  2.     def findTheWinner(self, n: int, k: int) -> int:
  3.         ans = 0
  4.         for i in range(1,n + 1):
  5.             ans = (ans + k) % i 
  6.         return ans + 1